ACM SIGACT News · 2008 · 162 citations · 9 references
ComputingComputer ScienceAlgorithmsCombinatoricsMatching TheoryRanking ProblemsBipartite MatchingCompetitive RatioMatching AlgorithmsMatching Problems
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 .
9
An optimal algorithm for on-line bipartite matching
Richard M. Karp, Umesh Vazirani, Vijay V. Vazirani · 1990 · 724 citations · Full text
AdWords and generalized online matching
Aranyak Mehta, Amin Saberi, Umesh Vazirani et al. · Journal of the ACM · 2007 · 622 citations
Combinatorial auctions with decreasing marginal utilities
Benny Lehmann, Daniel Lehmann, Noam Nisan · 2001 · 234 citations
Business, Economics, Mathematics +8
Allocating online advertisement space with unreliable estimates
Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi · 2007 · 132 citations
Business, Marketing, Advertising +11