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, namely that Ranking is $(1 - \frac{1}{e} - \alpha) $- c o m p e t i t i v e w i t h p r o b a b i l i t y a t l e a s t$ 1 - e^{-2 \alpha^2 n} $w h e r e$ 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.

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) $- c o m p e t i t i v e w i t h p r o b a b i l i t y a t l e a s t$ 1 - e^{-2 \alpha^2 n} $w h e r e$ 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.

文献摘要