On-line load balancing with applications to machine scheduling and virtual circuit routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On-line load balancing with applications to machine scheduling and virtual circuit routing

Full text

Pdf (789 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: 623 - 631

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

James Aspnes
Yossi Azar
Amos Fiat
Serge Plotkin
Orli Waarts

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 67, Citation Count: 44

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.167248 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	Y. Azar, A. Broder, and A. Karlin. On-line load balancing. In Proc. 33rd IEEE Annual Symposium on Foundations of Computer Science, pages 218-225, 1992.
	2	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
	3	Y. Azar, S. Plotkin, and O. Waarts. Routing of virtual circuits with limited duration. Unpublished Manuscript, March 1993.
	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	Bill Burley. Personal Communication, 1992.
	6	Ernest Davis , Jeffrey M. Jaffe, Algorithms for Scheduling Tasks on Unrelated Processors, Journal of the ACM (JACM), v.28 n.4, p.721-736, Oct. 1981 [doi>10.1145/322276.322284]
	7	R.L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45:1563- 1581, 1966.
	8	R.L. Graham, E.L. Lawler, j.K Lenstra, and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287-326, 1979.
	9	J.M. Jaffe. Efficient scheduling of tasks without full use of processor resources. Theoretical Computer Science, 12:1-17, 1980.
	10	B. Kalyanasundaram and K. Pruhs. Online load balancing of temporary tasks. Unpublished manuscript, March 1993.
	11	Tom Leighton , Clifford Stein , Fillia Makedon , Éva Tardos , Serge Plotkin , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.101-111, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103425]
	12	J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
	13	Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Proceedings of the 32nd annual symposium on Foundations of computer science, p.495-504, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185411]
	14	P Raghavan , C D Thompson, Provably good routing in graphs: regular arrays, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.79-87, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22154]
	15	Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
	16	David B. Shmoys , Joel Wein , David P. Williamson, Scheduling parallel machines on-line, Proceedings of the 32nd annual symposium on Foundations of computer science, p.131-140, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185361]
	17	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]

CITED BY 44

	Amotz Bar-Noy , Yishay Mansour , Baruch Schieber, Competitive dynamic bandwidth allocation, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.31-39, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	Jon Kleinberg , Yuval Rabani , Éva Tardos, Allocating bandwidth for bursty connections, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.664-673, May 04-06, 1997, El Paso, Texas, United States
	Yossi Azar , Oded Regev, On-line bin-stretching, Theoretical Computer Science, v.268 n.1, p.17-41, 10/06/2001
	Reinhard Lüling , Burkhard Monien, A dynamic distributed load balancing algorithm with provable good performance, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.164-172, June 30-July 02, 1993, Velen, Germany
	Adi Avidor , Yossi Azar , Jiří Sgall, Ancient and new algorithms for load balancing in the Lp norm, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.426-435, January 25-27, 1998, San Francisco, California, 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
	Ashish Goel , Adam Meyerson , Serge Plotkin, Approximate majorization and fair online load balancing, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.384-390, January 07-09, 2001, Washington, D.C., United States
	Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.189-197, May 01-04, 1999, Atlanta, Georgia, 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
	Keqin Li, Deterministic and randomized algorithms for distributed on-line task assignment and load balancing without load status information, Proceedings of the 1998 ACM symposium on Applied Computing, p.613-622, February 27-March 01, 1998, Atlanta, Georgia, United States
	Albert G. Greenberg , R. Srikant, Computational techniques for accurate performance evaluation of multirate, multihop communication networks, IEEE/ACM Transactions on Networking (TON), v.5 n.2, p.266-277, April 1997
	Ashish Goel , Adam Meyerson , Serge Plotkin, Distributed admission control, scheduling, and routing with stale information, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.611-619, January 07-09, 2001, Washington, D.C., United States
	Miklos Ajtai , James Aspnes , Moni Naor , Yuval Rabani , Leonard J. Schulman , Orli Waarts, Fairness in scheduling, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.477-485, January 22-24, 1995, San Francisco, California, United States
	Prabhakar Raghavan , Eli Upfal, Efficient routing in all-optical networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.134-143, May 23-25, 1994, Montreal, Quebec, Canada
	Amotz Bar-Noy , Ran Canetti , Shay Kutten , Yishay Mansour , Baruch Schieber, Bandwidth allocation with preemption, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.616-625, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Ashish Goel , Adam Meyerson , Serge Plotkin, Combining fairness with throughput: online routing with multiple objectives, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.670-679, May 21-23, 2000, Portland, Oregon, 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
	Baruch Awerbuch , Yair Bartal , Amos Fiat , Adi Rosén, Competitive non-preemptive call control, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.312-320, January 23-25, 1994, Arlington, Virginia, United States
	Ellen L. Hahne , Alexander Kesselman , Yishay Mansour, Competitve buffer management for shared-memory switches, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.53-58, July 2001, Crete Island, Greece
	Minos N. Garofalakis , Yannis E. Ioannidis , Banu Özden , Avi Silberschatz, Throughput-competitive admission control for continuous media databases, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.79-88, June 01-04, 1998, Seattle, Washington, United States
	Baruch Awerbuch , Yossi Azar, Competitive multicast routing, Wireless Networks, v.1 n.1, p.107-114, Feb. 1995
	Yair Amir , Baruch Awerbuch , R. Sean Borgstrom, A cost-benefit framework for online management of a metacomputing system, Proceedings of the first international conference on Information and computation economies, p.140-147, October 25-28, 1998, Charleston, South Carolina, United States
	Susanne Albers, Better bounds for online scheduling, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.130-139, May 04-06, 1997, El Paso, Texas, United States
	Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Anil Kamath , Omri Palmon , Serge Plotkin, Routing and admission control in general topology networks with Poisson arrivals, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 28-30, 1996, Atlanta, Georgia, United States
	Ashish Goel , Monika R. Henzinger , Serge Plotkin, Online througput-competitive algorithm for multicast routing and admission control, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.97-106, January 25-27, 1998, San Francisco, California, United States
	Stefano Leonardi , Alberto Marchetti-Spaccamela , Alessio Presciutti , Adi Rosén, On-line randomized call control revisited, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.323-332, January 25-27, 1998, San Francisco, California, United States
	Leah Epstein , Lene M. Favrholdt, On-line maximizing the number of items packed in variable-sized bins, Acta Cybernetica, v.16 n.1, p.57-66, January 2003
	Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer overflow management in QoS switches, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.520-529, July 2001, Hersonissos, Greece
	Adam Meyerson, Online algorithms for network design, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Jie Gao , Li Zhang, Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Dániel Orincsay , Balázs Szviatovszki , Géza Böhm, Prompt partial path optimization in MPLS networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.5, p.557-572, 5 December 2003
	Ashish Goel , Monika R. Henzinger , Serge Plotkin, An online throughput-competitive algorithm for multicast routing and admission control, Journal of Algorithms, v.55 n.1, p.1-20, April 2005
	Yigal Bejerano , Seung-Jae Han , Li (Erran) Li, Fairness and load balancing in wireless LANs using association control, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA
	Alexander Kesselman , Yishay Mansour, Harmonic buffer management policy for shared memory switches, Theoretical Computer Science, v.324 n.2-3, p.161-182, 20 September 2004
	Minos Garofalakis , Yannis Ioannidis , Banu Özden , Avi Silberschatz, Competitive on-line scheduling of continuous-media streams, Journal of Computer and System Sciences, v.64 n.2, p.219-248, March 2002
	Costas Busch , Malik Magdon-Ismail , Jing Xi, Oblivious routing on geometric networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Baruch Awerbuch , David Holmer , Herbert Rubens, The medium time metric: high throughput route selection in multi-rate ad hoc wireless networks, Mobile Networks and Applications, v.11 n.2, p.253-266, April 2006
	Narayanan Sadagopan , Mitali Singh , Bhaskar Krishnamachari, Decentralized utility-based sensor network design, Mobile Networks and Applications, v.11 n.3, p.341-350, June 2006
	Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Yigal Bejerano , Seung-Jae Han , Li Li, Fairness and load balancing in wireless LANs using association control, IEEE/ACM Transactions on Networking (TON), v.15 n.3, p.560-573, June 2007
	Mohammad Taghi Hajiaghayi , Robert D. Kleinberg , Harald Räcke , Tom Leighton, Oblivious routing on node-capacitated and directed graphs, ACM Transactions on Algorithms (TALG), v.3 n.4, p.51-es, November 2007
	Costas Busch , Malik Magdon-Ismail , Marios Mavronicolas, Efficient bufferless packet switching on trees and leveled networks, Journal of Parallel and Distributed Computing, v.67 n.11, p.1168-1186, November, 2007