Improvements in throughout maximization for real-time scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improvements in throughout maximization for real-time scheduling

Full text

Pdf (772 KB)

Source

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

Portland, Oregon, United States

Pages: 680 - 687

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Piotr Berman	Department of Computer Science & Engineering, Pennsylvania State University, University Park, PA
Bhaskar DasGupta	Department of Computer Science, Rutgers University, Camden, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 22, Citation Count: 4

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/335305.335401 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	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]
	2	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 [doi>10.1145/335305.335410]
	3	Amotz Bar-Noy , Sudipto Guha , Joseph (Seffi) Naor , Baruch Schieber, Approximating the throughput of multiple machines under real-time scheduling, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.622-631, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301420]
	4	Berman, P., Z. Zhang, J. Bouck and W. Miller, Large aligning two fragmented sequences, manuscript, submitted for journal publication.
	5	Kise H., T. Ibaraki and H. Mine, A solvable case of one machine scheduling problems with ready and due dates, Operations Research 26, 121-126, 1978.
	6	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]
	7	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]
	8	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
	9	Hang Liu , Magda El Zarki, Adaptive source rate control for real-time wireless video transmission, Mobile Networks and Applications, v.3 n.1, p.49-60, June 1998 [doi>10.1023/A:1019108328296]
	10	Overmars, M. H., Computational geometry on a grid: an overview, Theoretical Foundations of Computer Graphics and CAD, NATO ASI Series F40, Edited by R. A. Eaxnshaw, Springer-Verlag Berlin Heidelberg, 167-184, 1988.
	11	G. R. Rajugopal , R. H. M. Hafez, Adaptive rate controlled, robust video communication over packet wireless networks, Mobile Networks and Applications, v.3 n.1, p.33-47, June 1998 [doi>10.1023/A:1019156211458]
	12	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]
	13	Frits C. R. Spieksma, Approximating an Interval Scheduling Problem, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.169-180, July 18-19, 1998
	14	David K. Y. Yau , Simon S. Lam, Adaptive rate-controlled scheduling for multimedia applications, Proceedings of the fourth ACM international conference on Multimedia, p.129-140, November 18-22, 1996, Boston, Massachusetts, United States [doi>10.1145/244130.244177]

CITED BY 4

	Jae-Hoon Kim , Kyung-Yong Chwa, Online deadline scheduling on faster machines, Information Processing Letters, v.85 n.1, p.31-37, 16 January 2003
	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 , S. Muthukrishnan, Simple approximation algorithm for nonoverlapping local alignments, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.677-678, January 06-08, 2002, San Francisco, California
	Julia Chuzhoy , Rafail Ostrovsky , Yuval Rabani, Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems, Mathematics of Operations Research, v.31 n.4, p.730-738, November 2006