Scheduling data transfers in a network and the set scheduling problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Scheduling data transfers in a network and the set scheduling problem

Full text

Pdf (809 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: 189 - 197

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Ashish Goel	Department of Computer Science, Stanford University
Monika R. Henzinger	Compaq Systems Research Center, Palo Alto
Serge Plotkin	Department of Computer Science, Stanford University
Eva Tardos	Department of Computer Science, Cornell University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 17, Citation Count: 7

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.301300 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, and $. Plotkin. Throughput competitive online routing. &tth IEEE symposium on Foundations of Computer Science, pages 32-40, 1993.
	3	Yair Bartal , Amos Fiat , Stefano Leonardi, Lower bounds for on-line graph problems with application to on-line circuit and optical routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.531-540, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238001]
	4	James Beck , Daniel Siewiorek, Modeling Multicomputer Task Allocation as a Vector Packing Problem, Proceedings of the 9th international symposium on System synthesis, p.115, November 06-08, 1996
	5	Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
	6	Soumen Chakrabarti , Cynthia A. Phillips , Andreas S. Schulz , David B. Shmoys , Clifford Stein , Joel Wein, Improved Scheduling Algorithms for Minsum Criteria, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.646-657, July 08-12, 1996
	7	Chandra Chekuri , Sanjeev Khanna, On multi-dimensional packing problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.185-194, January 17-19, 1999, Baltimore, Maryland, United States
	8	C. Chekuri , R. Motwani , B. Natarajan , C. Stien, Approximation techniques for average completion time scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.609-618, January 05-07, 1997, New Orleans, Louisiana, United States
	9	Uriel Feige , Joe Kilian, Zero Knowledge and the Chromatic Number, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.278, May 24-27, 1996
	10	A. Feldmann, M. Kao, J. Stall, and S. Tent. Optimal online scheduling of parallel jobs with dependencies. J. of Combinatorial Optimization, 1(4):393-411, 1998.
	11	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
	12	J. Garay, I. Gopal, S. Kutten, Y. Mansour, and M. Yung. Efficient on-line call control algorithms. 2nd Annual Israel Conference on Theory of Computing and Systems, 1993.
	13	Minos N. Garofalakis , Yannis E. Ioannidis, Scheduling issues in multimedia query optimization, ACM Computing Surveys (CSUR), v.27 n.4, p.590-592, Dec. 1995 [doi>10.1145/234782.234797]
	14	Leslie A. Hall , Andreas S. Schulz , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, v.22 n.3, p.513-544, Aug. 1997 [doi>10.1287/moor.22.3.513]
	15	Leslie A. Hall , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.142-151, January 28-30, 1996, Atlanta, Georgia, United States
	16	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	17	Hans Kellerer , Thomas Tautenhahn , Gerhard J. Woeginger, Approximability and nonapproximability results for minimizing total flow time on a single machine, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.418-426, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237989]
	18	Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.110-119, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258562]
	19	Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258570]
	20	C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. Lecture Notes in Computer Science 955, pages 290-301, Springer, Berlin.
	21	Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
	22	Jiří Sgall, Randomized on-line scheduling of parallel jobs, Journal of Algorithms, v.21 n.1, p.149-175, July 1996 [doi>10.1006/jagm.1996.0041]

CITED BY 7

	Michael A. Bender , S. Muthukrishnan , Rajmohan Rajaraman, Improved algorithms for stretch scheduling, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.762-771, January 06-08, 2002, San Francisco, California
	Wenfei Fan , Minos Garofalakis , Ming Xiong , Xibei Jia, Composable XML integration grammars, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Journal of Algorithms, v.48 n.2, p.314-332, September 2003
	Michael A. Bender , S. Muthukrishnan , Rajmohan Rajaraman, Approximation Algorithms for Average Stretch Scheduling, Journal of Scheduling, v.7 n.3, p.195-222, May-June 2004
	Shanchieh Jay Yang , Gustavo de Veciana, Enhancing both network and user performance for networks supporting best effort traffic, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.349-360, April 2004
	Leah Epstein , Rob van Stee, Optimal on-line flow time with resource augmentation, Discrete Applied Mathematics, v.154 n.4, p.611-621, 15 March 2006
	Mohammed S. Eltayeb , Atakan Dogan , Fusun Ozguner, Concurrent Scheduling: Efficient Heuristics for Online Large-Scale Data Transfers in Distributed Real-Time Environments, IEEE Transactions on Parallel and Distributed Systems, v.17 n.11, p.1348-1359, November 2006