On-line bipartite matching made simple
- Resource Type
- Article
- Authors
- Birnbaum, Benjamin; Mathieu, Claire
- Source
- ACM SIGACT News; March 2008, Vol. 39 Issue: 1 p80-87, 8p
- Subject
- Language
- ISSN
- 01635700
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.