Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching
Lists
Only you see this
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...