Competitive Analysis of Online Algorithms

Delve into the second part of a comprehensive lecture on competitive analysis of online algorithms. Explore advanced concepts in decision-making under uncertainty, focusing on the competitive analysis framework. Compare the performance of online algorithms making decisions without future knowledge to the best dynamic sequence of decisions in hindsight. Examine representative problems, solution techniques, and proof strategies used in this vibrant area of computer science research. Learn from Anupam Gupta of Carnegie Mellon University as he continues to survey the field, building upon the foundations laid in Part 1 of this Data-Driven Decision Processes Boot Camp presentation at the Simons Institute.