Approximating the throughput of multiple machines under real-time scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating the throughput of multiple machines under real-time scheduling

Full text

Pdf (854 KB)

Source

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

Atlanta, Georgia, United States

Pages: 622 - 631

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Amotz Bar-Noy	Electrical Engineering Depatment, Tel Aviv University, Tel Aviv 69978, Israel
Sudipto Guha	Computer Science Department, Stanford University, Stanford, CA
Joseph (Seffi) Naor	Bell Laboratories, Lucent Technologies, 600 Mountain Ave., Murray Hill, NJ
Baruch Schieber	IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY

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): 37, Citation Count: 11

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/301250.301420 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	Micah Adler , Ramesh K. Sitaraman , Arnold L. Rosenberg , Walter Unger, Scheduling time-constrained communication in linear networks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.269-278, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277693]
	2	Susanne Albers , Naveen Garg , Stefano Leonardi, Minimizing stall time in single and parallel disk systems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.454-462, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276858]
	3	E. M. Arkin , E. B. Silverberg, Scheduling jobs with fixed start and end times, Discrete Applied Mathematics, v.18 n.1, p.1-8, Nov. 1987 [doi>10.1016/0166-218X(87)90037-0]
	4	Baruch Awerbuch , Yossi Azar , Amos Fiat , Stefano Leonardi , Adi Rosén, On-line Competive Algorithms for Call Admission in Optical Networks, Proceedings of the Fourth Annual European Symposium on Algorithms, p.431-444, September 25-27, 1996
	5	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
	6	Amotz Bar-Noy , Ran Canetti , Shay Kutten , Yishay Mansour , Baruch Schieber, Bandwidth Allocation with Preemption, SIAM Journal on Computing, v.28 n.5, p.1806-1828, April/May 1999 [doi>10.1137/S0097539797321237]
	7	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]
	8	Jacek Blazewicz, Scheduling in Computer and Manufacturing Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
	9	G. CORNUEJOLS, M. FISHER AND G. NEMHAUSER, Location of bank accounts to optimize float, Management Science, Vol, 23, pp. 789-8 t0,1977.
	10	Ulrich Faigle , Willem M. Nawijn, Note on scheduling intervals on-line, Discrete Applied Mathematics, v.58 n.1, p.13-17, March 10, 1995 [doi>10.1016/0166-218X(95)00112-5]
	11	Matteo Fischetti , Silvano Martello , Paolo Toth, The fixed job schedule problem with spread-time constraints, Operations Research, v.35 n.6, p.849-858, November-December 1987 [doi>10.1287/opre.35.6.849]
	12	Juan A. Garay , Inder S. Gopal , Shay Kutten , Yishay Mansour , Moti Yung, Efficient on-line call control algorithms, Journal of Algorithms, v.23 n.1, p.180-194, April 1997 [doi>10.1006/jagm.1996.0821]
	13	M.R. GAREY AND D.S. JOHNSON, Two processor scheduling with start times and deadlines, SIAM J. on Computing, Vol. 6, pp. 416-426, 1977.
	14	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	15	Sally A. Goldman , Jyoti Parwatikar , Subhash Suri, On-line Scheduling with Hard Deadlines (Extended Abstract), Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.258-271, August 06-08, 1997
	16	Michael H. Goldwasser, Patience is a virtue: the effect of slack on competitiveness for admission control, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.396-405, January 17-19, 1999, Baltimore, Maryland, United States
	17	N.G. HALL AND M.J. MAGAZINE, Maximizing the vatue of a space mission, European Journal of Operationaf Research, Vol. 78, pp. 224- 241, 1994.
	18	H. KISE, T. IBARAKI AND H. MINE, A solvabl~case of one machine scheduling problem with ready and due dates, Operation research, Vot. 26, pp. 121-126, 1978.
	19	Gilad Koren , Dennis Shasha, D^over: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems, SIAM Journal on Computing, v.24 n.2, p.318-339, April 1995 [doi>10.1137/S0097539792236882]
	20	E.L. LAWLER, Sequencingto minimize the weighted number of tardy jobs, Recherche Operationnel, Vol. l 0, pp. 27-33, ! 976.
	21	E. L. Lawler, A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs, Annals of Operations Research, v.26 n.1-4, p.125-133, Dec. 1990 [doi>10.1007/BF02248588]
	22	E.L. LAWLER, J.K. LENSTRA, A.H.G. RINNOOY KAN AND D.B. SHMOYS, "Sequencing and Scheduling: Algorithms and Complexity'', in Handbooks in Operations Research, Vol.4: Logistics for Production andlnventory (Eds. S.C. Graves, A.H.G. Rinnooy Kan and P.H. Zipkin), North HoIland, 1993.
	23	R. Lipton, Online interval scheduling, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.302-311, January 23-25, 1994, Arlington, Virginia, United States
	24	Sartaj K. Sahni, Algorithms for Scheduling Independent Tasks, Journal of the ACM (JACM), v.23 n.1, p.116-127, Jan. 1976 [doi>10.1145/321921.321934]
	25	J. WEIN, Personal Communication, 1999.
	26	Mihalis Yannakakis, On the approximation of maximum satisfiability, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.1-9, September 1992, Orlando, Florida, United States

CITED BY 11

	T. S. Jayram , Tracy Kimbrel , Robert Krauthgamer , Baruch Schieber , Maxim Sviridenko, Online server allocation in a server farm via benefit task systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.540-549, July 2001, Hersonissos, Greece
	Allan Borodin , Morten N. Nielsen , Charles Rackoff, (Incremental) priority algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.752-761, January 06-08, 2002, San Francisco, California
	Cynthia A. Phillips , R. N. Uma , Joel Wein, Off-line admission control for general scheduling problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.879-888, January 09-11, 2000, San Francisco, California, United States
	Michel X. Goemans , Martin Skutella, Cooperative facility location games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.76-85, January 09-11, 2000, San Francisco, California, United States
	Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.735-744, May 21-23, 2000, Portland, Oregon, United States
	Piotr Berman , Bhaskar DasGupta, Improvements in throughout maximization for real-time scheduling, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.680-687, May 21-23, 2000, Portland, Oregon, United States
	Junhyung Um , Jae-hoon Kim , Taewhan Kim, Layout-driven resource sharing in high-level synthesis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.614-618, November 10-14, 2002, San Jose, California
	Vamsi Veeramachaneni , Piotr Berman , Webb Miller, Aligning two fragmented sequences, Discrete Applied Mathematics, v.127 n.1, p.119-143, April 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
	Michel X. Goemans , Martin Skutella, Cooperative facility location games, Journal of Algorithms, v.50 n.2, p.194-214, February 2004
	Esther M. Arkin , Michael A. Bender , Joseph S. B. Mitchell , Steven S. Skiena, The Lazy Bureaucrat scheduling problem, Information and Computation, v.184 n.1, p.129-146, July 10, 2003