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