Center for Algorithms and Theory of Computation

CS 269S, Winter 2022: Theory Seminar


January 14, 2022, 1:00 – 1:50pm: online

Online Matching with High Probability

Thorben Tröbst

Abstract:

Randomized algorithms are typically analyzed wrt. their expected performance. This is because by simply repeating the algorithm often enough, one performs near that expected performance with high probability. However, online algorithms are often randomized and can, by definition, not be repeated. Thus it is of special interest to analyze randomized online algorithms wrt. the distribution of their performance. In this talk, I will show that the classic RANKING algorithm for the problem of Online Bipartite Matching is (1 - 1/e - o(1))-competitive with exponentially high probability. Building on this, I will also present similar results for other online matching problems.

Based on joint work with Milena Mihail: https://arxiv.org/abs/2112.07228