Competitive Analysis of Online Algorithms

The study of online algorithms forms a vibrant area of research in computer science — considering decision-making under uncertainty. One of the two dominant frameworks is that of competitive analysis. This framework compares the performance of an online algorithm that makes decisions without knowledge of the future with the performance of the best sequence of decisions in hindsight.

In this set of two talks in the Data-Driven Decision Processes Boot Camp, Anupam Gupta (Carnegie Mellon) defines the model, and surveys some representative problems, solution techniques, and proof strategies used in the competitive analysis of online algorithms.