On-line bipartite matching made simple

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.

REFERENCES

• 1: M. Agarwal and A. Puri. Base station scheduling of requests with fixed deadlines. In INFO-COM 2002: twenty-first annual joint conference of the IEEE Communications Societies, pages 487--496. IEEE, 2002.
• 2: Yossi Azar and Yoel Chaiutin. Optimal node routing. In Proceedings of STACS '06 (Lecture Notes in Computer Science 3884, pages 596--607. Springer, 2006.
• 3: Yossi Azar , Joseph (Seffi) Naor , Raphael Rom, The competitiveness of on-line assignments, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.203-210, September 1992, Orlando, Florida, United States
• 4: Yossi Azar and Yossi Richter. Management of multi-queue switches in QoS networks. Algorithmica, 43(1--2):81--96, 2005.
• 5: Avrim Blum , Tuomas Sandholm , Martin Zinkevich, Online algorithms for market clearing, Journal of the ACM (JACM), v.53 n.5, p.845-879, September 2006 [doi>10.1145/1183907.1183913]
• 6: Niv Buchbinder, Kamal Jain, and Joseph (Seffi) Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proceedings of ESA '07 (Lecture Notes in Computer Science 4698), pages 253--264. Springer, 2007.
• 7: Gagan Goel , Aranyak Mehta, Online budgeted matching in random input models with applications to Adwords, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.982-991, January 20-22, 2008, San Francisco, California
• 8: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
• 9: Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
• 10: Mohammad Mahdian , Hamid Nazerzadeh , Amin Saberi, Allocating online advertisement space with unreliable estimates, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250952]
• 11: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and generalized online matching, Journal of the ACM (JACM), v.54 n.5, p.22-es, October 2007 [doi>10.1145/1284320.1284321]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory