Title: Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching

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].