#
Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching

## Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg

## Presented by Jenny Lam

We give a simple proof that the ranking algorithm of Karp, Vazirani and Vazirani is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. The approach also generalizes easily to the vertex-weighted version considered by Agarwal et al. Further we show that the proof is very similar to the deterministic primal-dual argument for the online budgeted allocation problem with small bids (also called the AdWords problem) of Mehta et al.