Online load balancing and network flow

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Online load balancing and network flow

Full text

Pdf (881 KB)

Source

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

San Diego, California, United States

Pages: 402 - 411

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Steven Phillips
Jeffery Westbrook

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 28, Citation Count: 13

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/167088.167201 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.

	1	N. Alon, Generating pseudo-random permutations and maximum flow algorithms, Information Processing Letters, v.35 n.4, p.201-204, Aug. 1990 [doi>10.1016/0020-0190(90)90024-R]
	2	Y. Azar, A. Karlin, and A. Broder. Online load balancing. In Proc. 33nd Syrup. of Foundations of Computer Science, pages 218-225, 1992.
	3	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
	4	Yair Bartal , Amos Fiat , Howard Karloff , Rakesh Vohra, New algorithms for an ancient scheduling problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.51-58, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129718]
	5	J. Cheriyan and T. Hagerup. A randomized maximum flow algorithm. In Proceedings IEEE Symposium on Foundations of Computer Science, pages 118-123, 1989.
	6	Joseph Cheriyan , Torben Hagerup , Kurt Mehlhorn, Can a maximum flow be computed in o(nm) time?, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.235-248, July 1990, Warwick University, England
	7	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
	8	R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45:1563-1581, 1966.
	9	V. King , S. Rao , R. Tarjan, A faster deterministic maximum flow algorithm, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.157-164, September 1992, Orlando, Florida, United States
	10	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982

CITED BY 13

	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
	Petra Berenbrink , Friedhelm Meyer auf der Heide , Klaus Schröder, Allocating weighted jobs in parallel, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.302-310, June 23-25, 1997, Newport, Rhode Island, United States
	Ran Canetti , Sandy Irani, Bounding the power of preemption in randomized scheduling, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.606-615, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Amitai Armon , Yossi Azar , Leah Epstein , Oded Regev, Temporary tasks assignment resolved, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.116-124, January 06-08, 2002, San Francisco, California
	Harold N. Gabow, Algorithms for graphic polymatroids and parametric s-Sets, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.88-97, January 22-24, 1995, San Francisco, California, United States
	David R. Karger , Clifford Stein, An Õ(n²) algorithm for minimum cuts, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.757-765, May 16-18, 1993, San Diego, California, United States
	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
	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
	Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998
	Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Selfish load balancing and atomic congestion games, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Tak-Wah Lam , Hing-Fung Ting , Kar-Keung To , Wai-Ha Wong, On-line load balancing of temporary tasks revisited, Theoretical Computer Science, v.270 n.1-2, p.325-340, January
	David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996
	Wei-Chang Yeh, A simple Monte-Carlo method for estimating the continuous-state two-terminal network reliability at required demand level, Proceedings of the 2007 annual Conference on International Conference on Computer Engineering and Applications, p.164-170, January 17-19, 2007, Gold Coast, Queensland, Australia