Talks
Fall 2022

Competitive Analysis of Online Algorithms (Parts 1 and 2)

Wednesday, August 24th, 2022, 9:30 am10:30 am

Add to Calendar

Speaker: 

Anupam Gupta (Carnegie Mellon University)

Location: 

Calvin Lab Auditorium

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 making decisions (without knowledge of the future) to the performance of the best (dynamic) sequence of decisions in hindsight. (This is as opposed to the best static decision.) In these two talks, I will define the model, and survey some representative problems, solution techniques, and proof strategies used in the competitive analysis of online algorithms.