CS 269S, Fall 2013: Theory Seminar
Bren Hall, Room 1422, 1pm
December 6, 2013:

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.