Algorithms for minimizing weighted flow time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for minimizing weighted flow time

Full text

Pdf (251 KB)

Source

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

Hersonissos, Greece

Pages: 84 - 93

Year of Publication: 2001

ISBN:1-58113-349-9

Authors

Chandra Chekuri	Bell Labs, 600 Mountain Ave, Murray Hill, NJ
Sanjeev Khanna	Dept. of CIS, University of Pennsylvania, Philadelphia, PA
An Zhu	Dept. of Computer Science, Stanford University, Stanford, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 43, Citation Count: 23

Additional Information:

abstract 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/380752.380778 What is a DOI?

ABSTRACT

We study the problem of minimizing weighted flow time on a single machine in the preemptive setting. We present an O(\log^2 P)-competitive semi-online algorithm where P is the ratio of the maximum and minimum processing times of jobs in the system. In the offline setting we show that a (2+\eps)-approximation is achievable in quasi-polynomial time. These are the first non-trivial results for the weighted versions of minimizing flow time. For multiple machines we show that no competitive randomized online algorithm exists for weighted flow time. We also present an improved online algorithm for minimizing total stretch (a special case of weighted flow time) on multiple machines.

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	Foto Afrati , Evripidis Bampis , Chandra Chekuri , David Karger , Claire Kenyon , Sanjeev Khanna , Ioannis Milis , Maurice Queyranne , Martin Skutella , Cliff Stein , Maxim Sviridenko, Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.32, October 17-18, 1999
	2	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 [doi>10.1145/301250.301304]
	3	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
	4	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
	5	C. Chekuri and S. Khanna. Approximation schemes for preemptive weighted ow time. Manuscript, 2001.
	6	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]
	7	B. Kalyanasundaram and K. Pruhs. Speed is equivalent toclairvoyance. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 115-124, 1995.
	8	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]
	9	J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker. Complexity ofmachine scheduling problems. Annals of Discrete Mathematics, 1:343-362, 1977.
	10	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]
	11	S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
	12	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]

CITED BY 23

	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
	Leah Epstein , Rob van Stee, Lower bounds for on-line single-machine scheduling, Theoretical Computer Science, v.299 n.1-3, p.439-450, 18 April 2003
	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
	Nikhil Bansal , Kirk Pruhs, Server scheduling in the L_p norm: a rising tide lifts all boat, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	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
	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
	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
	N. Bansal , K. Dhamdhere, Minimizing weighted flow time, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	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
	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
	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
	Kirk Pruhs, Competitive online scheduling for server systems, ACM SIGMETRICS Performance Evaluation Review, v.34 n.4, March 2007
	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
	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
	Chetan Gupta , Abhay Mehta , Song Wang , Umesh Dayal, Fair, effective, efficient and differentiated scheduling in an enterprise data warehouse, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	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
	L. Amar , A. Mu'alem , J. Stosser, On the importance of migration for fairness in online grid markets, Proceedings of the 2008 9th IEEE/ACM International Conference on Grid Computing, p.65-74, September 29-October 01, 2008