In the study of online optimization, we seek to determine how well an algorithm can perform when the problem input is presented in sequential pieces, and the algorithm must make decisions immediately without knowledge of the future. We measure performance via the competitive ratio, i.e. the ratio of the algorithm's expected objective to that of the hindsight optimum. While many powerful techniques have been developed to design and analyze online algorithms, they are often tailored to specific problems. This motivates the general question: Can we develop unified methods for competitive analysis across problem settings?
In this talk, I will present a new framework based on Yao's minimax principle which recovers and extends known competitive bounds for many classic fractional online problems. The key idea is that, via minimax, we can reduce worse-case analysis to a setting where the input sequence is drawn from a known distribution. From here, our guiding rule is posterior matching: At each time, we choose the action that most closely tracks the action of the expected hindsight optimum conditioned on the observed past. Surprisingly, this single algorithmic principle proves to be optimal or near optimal across vastly different problem settings, including set cover, load balancing, matching, resource allocation, and more!
This is joint work with Thomas Kesselheim, Marco Molinaro, and Sahil Singla.
