Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching

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

Abstract

We give a simple proof that the ranking algorithm of Karp, Vazirani and Vazirani [KVV90] 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. [AGKM11]. 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. [MSVV05].
BibTeX
@inproceedings{devanur2013randomized,
  author = {Nikhil R. Devanur and Kamal Jain and Robert D. Kleinberg},
  title = {{Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching}},
  booktitle = {SODA},
  year = {2013},
  doi = {10.1137/1.9781611973105.7},
}

Loading related content...

Figure