Approximating total flow time on parallel machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating total flow time on parallel machines

Full text

Pdf (1.36 MB)

Source

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

El Paso, Texas, United States

Pages: 110 - 119

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Stefano Leonardi	Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza"
Danny Raz	International Computer Science Institute (ICSI), Berkeley

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 23, Citation Count: 45

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/258533.258562 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.

	B74	K.R. Baker. Introduction to Sequencing and Scheduling. Wiley, New York, 1974.
	DLY90	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]
	GJ76	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
	H96	Leslie A. Hall, Approximation algorithms for scheduling, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	KTW96	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]
	HSSW96	L.A. Hall, A.S. Schulz, D.B. Shmoys and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. Journal submission, 1995.
	LLRS90	E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys. Sequencing and Scheduling: Algorithms and Complexity. Handbooks in Operations Research and Management Science, Vol. ~: Logistics of Production and Inventory, 1990.
	L77	J.K. Lenstra. Sequencing by Enumerative Methods. Mathematical Centre Tracts 69 (Mathematisch Centrum, Amsterdam, 1977).
	PSTW97	C.A. Phillips, C. Stein, E. Torng and J. Wein. Approaching optimality via resource augmentation in time-critical scheduling. STOC97, this proceedings:

CITED BY 45

	Sachin More , S. Muthukrishnan , Elizabeth Shriver, Efficiently sequencing tape-resident jobs, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.33-43, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	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
	Chandra Chekuri , Sanjeev Khanna, Approximation schemes for preemptive weighted flow time, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Martin Skutella , Gerhard J. Woeginger, A PTAS for minimizing the weighted sum of job completion times on parallel machines, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.400-407, May 01-04, 1999, Atlanta, Georgia, United States
	Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States
	Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.189-197, May 01-04, 1999, Atlanta, Georgia, United States
	Baruch Awerbuch , Yossi Azar , Stefano Leonardi , Oded Regev, Minimizing the flow time without migration, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.198-205, May 01-04, 1999, Atlanta, Georgia, United States
	Uwe Schwiegelshohn , Ramin Yahyapour, Analysis of first-come-first-serve parallel job scheduling, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.629-638, January 25-27, 1998, San Francisco, California, United States
	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
	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
	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
	Wojciech Jawor, Three dozen papers on online algorithms, ACM SIGACT News, v.36 n.1, March 2005
	David P. Bunde, SPT is optimally competitive for uniprocessor flow, Information Processing Letters, v.90 n.5, p.233-238, 15 June 2004
	Jae-Hoon Kim , Kyung-Yong Chwa, Non-clairvoyant scheduling for weighted flow time, Information Processing Letters, v.87 n.1, p.31-37, 16 July 2003
	Bala Kalyanasundaram , Kirk R. Pruhs, Minimizing flow time nonclairvoyantly, Journal of the ACM (JACM), v.50 n.4, p.551-567, July 2003
	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
	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
	Luca Becchetti , Stefano Leonardi, Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines, Journal of the ACM (JACM), v.51 n.4, p.517-539, July 2004
	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
	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
	Jason McCullough , Eric Torng, SRPT optimally utilizes faster machines to minimize flow time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Luca Becchetti , Stefano Leonardi , Alberto Marchetti-Spaccamela , Kirk Pruhs, Semi-clairvoyant scheduling, Theoretical Computer Science, v.324 n.2-3, p.325-335, 20 September 2004
	Dror G. Feitelson , Ahuva W. Mu'alem, On the definition of "on-line" in job scheduling problems, ACM SIGACT News, v.36 n.1, p.122-131, March 2005
	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
	Y. Guo , A. Lim , B. Rodrigues , S. Yu, Minimizing total flow time in single machine environment with release time: an experimental analysis, Computers and Industrial Engineering, v.47 n.2-3, p.123-140, November 2004
	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
	F. Afrati , I. Milis, Designing PTASs for MIN-SUM scheduling problems, Discrete Applied Mathematics, v.154 n.4, p.622-639, 15 March 2006
	Wun-Tat Chan , Tak-Wah Lam , Kin-Shing Liu , Prudence W. H. Wong, New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling, Theoretical Computer Science, v.359 n.1, p.430-439, 14 August 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
	Luca Becchetti , Stefano Leonardi , Alberto Marchetti-Spaccamela , Guido Schfer , Tjark Vredeveld, Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm, Mathematics of Operations Research, v.31 n.1, p.85-108, February 2006
	Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Journal of Computer and System Sciences, v.73 n.6, p.875-891, September, 2007
	Rabia Nessah , Chengbin Chu , Farouk Yalaoui, An exact method for Pm/sds,ri/Σ_i=1ⁿC_{i_{problem, Computers and Operations Research, v.34 n.9, p.2840-2848, September, 2007}}
	Kirk Pruhs, Competitive online scheduling for server systems, ACM SIGMETRICS Performance Evaluation Review, v.34 n.4, March 2007
	Olaf Arndt , Bernd Freisleben , Thilo Kielmann , Frank Thilo, A comparative study of online scheduling algorithms for networks of workstations, Cluster Computing, v.3 n.2, p.95-112, 2000
	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
	Tak-Wah Lam , Lap-Kei Lee , Isaac K. K. To , Prudence W. H. Wong, Competitive non-migratory scheduling for flow time and energy, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Eric Torng , Jason McCullough, SRPT optimally utilizes faster machines to minimize flow time, ACM Transactions on Algorithms (TALG), v.5 n.1, p.1-25, November 2008
	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