Online Matching with High Probability

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 (Theorem 1), 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 several generalizations of the Online Bipartite Matching Problem, including the Fully Online Matching Problem and the Online Vertex-Weighted Bipartite Matching Problem.