An optimal algorithm for on-line bipartite matching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An optimal algorithm for on-line bipartite matching

Full text

Pdf (559 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 352 - 358

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

R. M. Karp	University of California at Berkeley & International Computer Science Institute
U. V. Vazirani	Cornell University
V. V. Vazirani

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 131, Citation Count: 31

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/100216.100262 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BeBoKaTaWi	S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
	CoGaJo	E. G. Coffman, M. R. Garey, D. S. Johnson, 'Dynamic Bin Packing', SIAM J. comput., vol 12, 1983, pp. 227-258.
	Gy,Le	A. Gyarfas, J. Lehel, 'Online and First Fit Colorings of Graphs', J. Graph theory, Vol. 12, No. 2, pp. 217- 227, 1988.
	Ku	T. G. Kurtz, "Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes', Journal of Applied Probability, vol. 7, 1970, pp. 49-58.
	MaMcSl	Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
	Sl,Ta	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	Ya	A.C. Yao, "Probabilistic Computations: Towards a Unified Measure of Complexity', FOCS 1977, pp. 222- 227.

CITED BY 31

	Baruch Awerbuch , Yossi Azar , Amos Fiat , Tom Leighton, Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.519-530, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Baruch Awerbuch , Yossi Azar , Serge Plotkin , Orli Waarts, Competitive routing of virtual circuits with unknown duration, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.321-327, January 23-25, 1994, Arlington, Virginia, United States
	Marco Riedel, Online request server matching, Theoretical Computer Science, v.268 n.1, p.145-160, 10/06/2001
	Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High-speed switch scheduling for local-area networks, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.319-352, Nov. 1993
	Haim Kaplan , Mario Szegedy, On-line complexity of monotone set systems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.507-516, January 17-19, 1999, Baltimore, Maryland, United States
	Yair Bartal , Amos Fiat , Stefano Leonardi, Lower bounds for on-line graph problems with application to on-line circuit and optical routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.531-540, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Yossi Azar , Joseph 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
	Bala Kalyanasundaram , Kirk Pruhs, On-line weighted matching, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.234-240, January 28-30, 1991, San Francisco, California, United States
	Petra Berenbrink , Marco Riedel , Christian Scheideler, Simple competitive request scheduling strategies, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.33-42, June 27-30, 1999, Saint Malo, France
	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada
	Michael Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1094-1104, October 2001
	James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997
	Michael Mitzenmacher, On the analysis of randomized load balancing schemes, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.292-301, June 23-25, 1997, Newport, Rhode Island, United States
	Avrim Blum , Tuomas Sandholm , Martin Zinkevich, Online algorithms for market clearing, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.971-980, January 06-08, 2002, San Francisco, California
	Yossi Azar , Yossi Richter, Management of multi-queue switches in QoS networks, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High speed switch scheduling for local area networks, ACM SIGPLAN Notices, v.27 n.9, p.98-110, Sept. 1992
	Michael Mitzenmacher, Analyses of load stealing models based on differential equations, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.212-221, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Adam Meyerson , Akash Nanavati , Laura Poplawski, Randomized online algorithms for minimum metric bipartite matching, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.954-959, January 22-26, 2006, Miami, Florida
	Shahar Dobzinski , Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1064-1073, January 22-26, 2006, Miami, Florida
	Michael Mitzenmacher, Studying Balanced Allocations with Differential Equations, Combinatorics, Probability and Computing, v.8 n.5, p.473-482, September 1999
	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
	Ameet Kini , Srinath Shankar , Jeffrey F. Naughton , David J. Dewitt, Database support for matching: limitations and opportunities, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	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
	Nikhil R. Devenur , Thomas P. Hayes, The adwords problem: online keyword matching with budgeted bidders under random permutations, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA
	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
	Benjamin Birnbaum , Claire Mathieu, On-line bipartite matching made simple, ACM SIGACT News, v.39 n.1, March 2008
	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
	Karyn Benson , Benjamin Birnbaum , Esteban Molina-Estolano , Ran Libeskind-Hadas, Competitive analysis of online traffic grooming in WDM rings, IEEE/ACM Transactions on Networking (TON), v.16 n.4, p.984-997, August 2008
	Marek Chrobak, SIGACT news online algorithms column 13: 2007 - an offine perspective, ACM SIGACT News, v.39 n.3, September 2008
	Niv Buchbinder , Joseph (Seffi) Naor, Online Primal-Dual Algorithms for Covering and Packing, Mathematics of Operations Research, v.34 n.2, p.270-286, May 2009
	Niv Buchbinder , Joseph (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal: Dual Approach, Foundations and Trends® in Theoretical Computer Science, v.3 n.2$#8211;3, p.93-263, February 2009