Online Algorithm Design Beyond the Worst Case

Abstract

The analysis of algorithm performance in the worst-case has long been the gold standard of theoretical computer science: it provides a simple, compelling, and robust model, which can often be predictive as well as descriptive. That said, in recent years we have seen an exciting surge in analyzing algorithms using models that go beyond the worst case. Particularly, how can we use ideas from machine learning to inform algorithm design?

In this talk we will discuss some of the results and techniques that come out of this endeavor, in both offline and online settings. For example, we will study covering problems like set cover, load balancing problems like scheduling jobs of machines, and cut problems. We will see some of the modeling decisions in beyond worst-case frameworks, as well as the algorithmic ideas – some old, some new – that can be used to give more nuanced guarantees for these classical problems, complementing our understanding of these problem in the worst-case settings.