Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk)

Analyzing the performance of algorithms in both the worst case and the average case are cornerstones of computer science: these are two different ways to understand how well algorithms perform. Over the past two decades, there has been a concerted effort to understand the performance of algorithms in models that go beyond these two extremes. In this talk I will discuss some of the proposed models and approaches, particularly for problems related to online algorithms, where decisions must be made sequentially without knowing future portions of the input