Minimizing the flow time without migration

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimizing the flow time without migration

Full text

Pdf (536 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: 198 - 205

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Baruch Awerbuch	Johns Hopkins University, Baltimore, MD and MIT Lab. for Computer Science
Yossi Azar	Department of Computer Science, Tel Aviv University, Tel-Aviv, 69978, Israel
Stefano Leonardi	Departimento di Informatica Sistemistica, Università di Roma, "La Sapienza", via Salaria 113, 00198-Roma, Italia
Oded Regev	Department of Computer Science, Tel Aviv University

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): 18, Citation Count: 20

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.301304 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	K.R. Baker. Introduction to Sequencing and Scheduling. Wiley, 1974.
	2	J. Du , J. Y.-I. Leung , G. H. Young, Minimizing mean flow time with release time constraint, Theoretical Computer Science, v.75 n.3, p.347-355, Oct. 1990 [doi>10.1016/0304-3975(90)90100-V]
	3	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
	4	Leslie A. Hall, Approximation algorithms for scheduling, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	5	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]
	6	E.L. Lawler, J.K Lenstra, A.H.G. Rinnooy Kan, and D.!~. Shmoys. Sequencing and scheduling: algorithms and comptexity. In Handbooks in operations research and management science, volume 4, pages 445-522. North Holland, 1993.
	7	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]

CITED BY 20

	Chandra Chekuri , Sanjeev Khanna , An Zhu, Algorithms for minimizing weighted flow time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.84-93, July 2001, Hersonissos, Greece
	Luca Becchetti , Stefano Leonardi, Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.94-103, July 2001, Hersonissos, Greece
	Luca Becchetti , Stefano Leonardi , S. Muthukrishnan, Scheduling to minimize average stretch without migration, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 09-11, 2000, San Francisco, California, United States
	David P. Bunde, SPT is optimally competitive for uniprocessor flow, Information Processing Letters, v.90 n.5, p.233-238, 15 June 2004
	Michael A. Bender , Michael O. Rabin, Scheduling Cilk multithreaded parallel programs on processors of different speeds, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.13-21, July 09-13, 2000, Bar Harbor, Maine, United States
	Zahir Tari , James Broberg , Albert Y. Zomaya , Roberto Baldoni, A least flow-time first load sharing approach for distributed server farm, Journal of Parallel and Distributed Computing, v.65 n.7, p.832-842, July 2005
	Luca Becchetti , Stefano Leonardi , S. Muthukrishnan, Average stretch without migration, Journal of Computer and System Sciences, v.68 n.1, p.80-95, February 2004
	Jens S. Frederiksen , Kim S. Larsen , John Noga , Patchrawat Uthaisombut, Dynamic TCP acknowledgment in the LogP model, Journal of Algorithms, v.48 n.2, p.407-428, September 2003
	Chandra Chekuri , Ashish Goel , Sanjeev Khanna , Amit Kumar, Multi-processor scheduling to minimize flow time with ε resource augmentation, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, 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
	Ho-Leung Chan , Tak-Wah Lam , Kin-Shing Liu, Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.334-343, January 22-26, 2006, Miami, Florida
	Nir Avrahami , Yossi Azar, Minimizing total flow time and total completion time with immediate dispatching, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Monaldo Mastrolilli, Notes on max flow time minimization with controllable processing times, Computing, v.71 n.4, p.375-386, December 2003
	Nikhil Bansal, On minimizing the total flow time on multiple machines, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Naveen Garg , Amit Kumar, Minimizing average flow time on related machines, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Nikhil Bansal , Ho-Leung Chan, Weighted flow time does not admit O(1)-competitive algorithms, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1238-1244, January 04-06, 2009, New York, New York
	Nikhil Bansal , Kedar Dhamdhere, Minimizing weighted flow time, ACM Transactions on Algorithms (TALG), v.3 n.4, p.39-es, November 2007
	Marta Beltrán , Antonio Guzmán, How to Balance the Load on Heterogeneous Clusters, International Journal of High Performance Computing Applications, v.23 n.1, p.99-118, February 2009
	Jivitej S. Chadha , Naveen Garg , Amit Kumar , V. N. Muralidhara, A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA