Bounding the power of preemption in randomized scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bounding the power of preemption in randomized scheduling

Full text

Pdf (1.12 MB)

Source

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

Las Vegas, Nevada, United States

Pages: 606 - 615

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Ran Canetti	Dept. of Applied Mathematics and Computer Science, Weizmann Institute, Israel
Sandy Irani	Department of Information and Computer Science, University of California, Irvine, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 23, Citation Count: 3

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/225058.225278 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	James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line load balancing with applications to machine scheduling and virtual circuit routing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.623-631, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167248]
	2	B. Awerbuch, Y. Azar, S. Plotkin. Throughput-competitive online routing. In 34th IEEE Symposium on Foundations of Computer Science, 1993. 32-40.
	3	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
	4	B. Awerbuch, R. Gawlick, T. Leighton, Y. Rabani. On-line admission control and circuit routing for high per-formance computing and communication. To appear in Proc. 35th Annual Symposium on the Foundations of Computer Science, 1994.
	5	Y. Azar, A.Z. Broder, A.R. Karlin. Online load bal-ancing. In Proc. .33rd Annual Symposium on the Foun-dations of Computer Science, 1992, pages 218-225.
	6	Yossi Azar , Bala Kalyanasundaram , Serge A. Plotkin , Kirk Pruhs , Orli Waarts, Online Load Balancing of Temporary Tasks, Proceedings of the Third Workshop on Algorithms and Data Structures, p.119-130, August 11-13, 1993
	7	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
	8	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 [doi>10.1145/225058.225279]
	9	Yair Bartal , Amos Fiat , Howard Karloff , Rakesh Vohra, New algorithms for an ancient scheduling problem, Journal of Computer and System Sciences, v.51 n.3, p.359-366, Dec. 1995 [doi>10.1006/jcss.1995.1074]
	10	S. Baruah , G. Koren , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha, On-line scheduling in the presence of overload, Proceedings of the 32nd annual symposium on Foundations of computer science, p.100-110, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185354]
	11	S. Baruah , G. Koren , D. Mao , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha , F. Wang, On the competitiveness of on-line real-time task scheduling, Real-Time Systems, v.4 n.2, p.125-144, May 1992 [doi>10.1007/BF00365406]
	12	R. Canetti, S. Irani. Bounding the power of preemption in randomized scheduling. Technical Report, ICS 95-07, University of California, Irvine.
	13	Juan A. Garay , Inder S. Gopal, Call preemption in communication networks, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.1043-1050, May 1992, Florence, Italy
	14	J. Garay, 1.S. Gopal, S. Kutten, Y. h4ansour, M. Yung. Efficient on-line call control algorithms. In Proc. 2nd Israel Symposium on Theory of Computing and SW-tems, pages 285-293, June 1993.
	15	R.L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journul on .4pplied Mathematics, 17:416-429,1969.
	16	David R. Karger , Steven J. Phillips , Eric Torng, A better algorithm for an ancient scheduling problem, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.132-140, January 23-25, 1994, Arlington, Virginia, United States
	17	G. Koren and D. Shasha. D"'": An optimal on-line scheduling algorithm for overloaded real-time systems. Technical Report 594, Courant Institute, New York University, 1992.
	18	Gilad Koren , Dennis Shasha, MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling, Theoretical Computer Science, v.128 n.1-2, p.75-97, June 6, 1994 [doi>10.1016/0304-3975(94)90165-1]
	19	Rajeev Motwani , Steven Phillips , Eric Torng, Non-clairvoyant scheduling, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.422-431, January 25-27, 1993, Austin, Texas, United States
	20	Steven Phillips , Jeffery Westbrook, Online load balancing and network flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.402-411, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167201]
	21	K. K. Ramakrishnan , Lev Vaitzblit , Cary G. Gray , Uresh Vahalia , Dennis Ting , Percy Tzelnic , Steve Glaser , Wayne Duso, Operating System Support for a Video-On-Demand File Service, Proceedings of the 4th International Workshop on Network and Operating System Support for Digital Audio and Video, p.216-227, November 03-05, 1993
	22	Gerhard J. Woeginger, On-line scheduling of jobs with fixed start and end times, Theoretical Computer Science, v.130 n.1, p.5-16, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90150-3]
	23	Special Issue on Asynchronous Transfer Mode. Int. Journal of Digital and Analog Cabled Systems, 1(4), 1988.

CITED BY 3

	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
	Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 17-19, 1999, Baltimore, Maryland, United States
	Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Journal of Scheduling, v.6 n.2, p.113-129, March/April 2003