On-line bipartite matching made simple
ACM SIGACT News2008Vol. 39(1), pp. 80–87
Citations Over TimeTop 10% of 2008 papers
Abstract
We examine the classic on-line bipartite matching problem studied by Karp, Vazirani, and Vazirani [8] and provide a simple proof of their result that the Ranking algorithm for this problem achieves a competitive ratio of 1 -- 1/ e .