Online Matching with High Probability

Abstract

We study the classical, randomized Ranking algorithm which is known to be $(1-\frac{1}{e})$-competitive in expectation for the Online Bipartite Matching Problem. We give a tail inequality bound, namely that Ranking is $(1-\frac{1}{e}-\alpha )$-competitive with probability at least $1-e^{-2{\alpha }^{2}n}$ where $n$ is the size of the maximum matching in the instance. Building on this, we show similar concentration results for the Fully Online Matching Problem and for the Online Vertex-Weighted Bipartite Matching Problem.

12 pages