Randomized Primal-Dual analysis of Ranking for Online Bipartite Matching

In the Online Bipartite Matching Problem, we are given a bipartite graph (S \cup T, E), where S denotes the set of client and T denotes the set of servers. The client come in one at a time with a subset of servers they can connect to. The problem ask for an assignment of clients to servers to maximize the number of client that can be served subject to the constraint that each server can serve at most 1 client. Karp, Vazirani and Vazirani proposed a simple Ranking algorithm to achieve an optimal (1-1/e)-competitive ratio. While the algorithm is very simple, the analysis is very complex. In this paper, the authors introduced a novel technique of randomized primal-dual analysis and give an simplified proof for the competitive ratio the ranking algorithm.

The speaker is presenting the work of Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg which can be found:
http://www.cs.cornell.edu/courses/CS6820/2012fa/handouts/djk.pdf