On-line bipartite matching made simple
Benjamin Birnbaum, Claire Mathieu · ACM SIGACT News · 2008
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 .