skip to main content
10.5555/1496770.1496904guideproceedingsArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article
Free access

Weighted flow time does not admit O(1)-competitive algorithms

Published: 04 January 2009 Publication History

Abstract

We consider the classic online scheduling problem of minimizing the total weighted flow time on a single machine with preemptions. Here, each job j has an arbitrary arrival time rj, weight wj and size pj, and given a schedule its flow time is defined as the duration of time since its arrival until it completes its service requirement. The first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently, and it was widely believed that the problem admits a constant factor competitive algorithm. In this paper, we show an ω(1) lower bound on the competitive ratio of any deterministic online algorithm. Our result is based on a gap amplification technique for online algorithms. Starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly.

References

[1]
F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Millis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 32--43, 1999.
[2]
N. Avrahami and Y. Azar. Minimizing total flow time and completion time with immediate dispacthing. In Proceedings of 15th SPAA, pages 11--18, 2003.
[3]
B. Awerbuch, Y. Azar, S. Leonardi, and O. Regev. Minimizing the flow time without migration. In ACM Symposium on Theory of Computing (STOC), pages 198--205, 1999.
[4]
N. Bansal. Minimizing flow time on a constant number of machines with preemption. Oper. Res. Lett., 33:267--273, 2005.
[5]
N. Bansal and K. Dhamdhere. Minimizing weighted flow time. ACM Transactions on Algorithms, (SODA 2002 and 2003 special issue), 3(4), 2007.
[6]
N. Bansal and K. Pruhs. Server scheduling in the lp norm: A rising tide lifts all boats. In ACM Symposium on Theory of Computing (STOC), pages 242--250, 2003.
[7]
L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, and K. Pruhs. Online weighted flow time and deadline scheduling. In Proceedings of RANDOM-APPROX, pages 36--47, 2001.
[8]
M. Bender, S. Muthukrishnan, and R. Rajaraman. Improved algorithms for stretch scheduling. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002.
[9]
C. Chekuri, A. Goel, S. Khanna, and A. Kumar. Multiprocessor scheduling to minimize flow time with epsilon resource augmentation. In ACM Symposium on Theory of Computing (STOC), pages 363--372, 2004.
[10]
C. Chekuri and S. Khanna. Approximation schemes for preemptive weighted flow time. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 297--305, 2002.
[11]
C. Chekuri, S. Khanna, and A. Zhu. Algorithms for minimizing weighted flow time. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 84--93, 2001.
[12]
H. Kellerer, T. Tautenhahn, and G. J. Woeginger. Approximability and nonapproximability results for minimizing total flow time on a single machine. In ACM Symposium on Theory of Computing (STOC), pages 418--426, 1996.
[13]
J. Lenstra, A. Kan, and P. Brucker. Complexity of machine scheduling problems. In Annals of Discrete Mathematics, number 1, pages 343--362, 1977.
[14]
S. Leonardi and D. Raz. Approximating total flow time on parallel machines. In ACM Symposium on Theory of Computing (STOC), pages 110--119, 1997.
[15]
R. Motwani, S. Phillips, and E. Torng. Nonclairvoyant scheduling. Theoretical Computer Science, 130(1):17--47, 1994.
[16]
S. Muthukrishnan, R. Rajaraman, A. Shaheen, and J. Gehrke. Online scheduling to minimize average stretch. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 433--442, 1999.
[17]
K. Pruhs. Competitive online scheduling for server systems. ACM SIGMETRICS Perform. Eval. Rev., 34(4):52--58, 2007.
[18]
K. Pruhs, J. Sgall, and E. Torng. Online scheduling. Chapter 35, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, 2004.

Cited By

View all
  • (2023)Energy-efficient scheduling with predictionsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669577(79012-79023)Online publication date: 10-Dec-2023
  • (2023)A PTAS for Minimizing Weighted Flow Time on a Single MachineProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585146(1335-1344)Online publication date: 2-Jun-2023
  • (2020)Scheduling Flows on a Switch to Optimize Response TimesProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400218(305-315)Online publication date: 6-Jul-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms
January 2009
1297 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 04 January 2009

Qualifiers

  • Research-article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)33
  • Downloads (Last 6 weeks)12
Reflects downloads up to 10 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Energy-efficient scheduling with predictionsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669577(79012-79023)Online publication date: 10-Dec-2023
  • (2023)A PTAS for Minimizing Weighted Flow Time on a Single MachineProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585146(1335-1344)Online publication date: 2-Jun-2023
  • (2020)Scheduling Flows on a Switch to Optimize Response TimesProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400218(305-315)Online publication date: 6-Jul-2020
  • (2019)A polynomial time constant approximation for minimizing total weighted flow-timeProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310531(1585-1595)Online publication date: 6-Jan-2019
  • (2018)SIGACT News Online Algorithms Column 34ACM SIGACT News10.1145/3300150.330016049:4(36-45)Online publication date: 15-Dec-2018
  • (2017)Competitive Algorithms from Competitive EquilibriaJournal of the ACM10.1145/313675465:1(1-33)Online publication date: 11-Dec-2017
  • (2014)Competitive algorithms from competitive equilibriaProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591814(313-322)Online publication date: 31-May-2014
  • (2013)Weighted flowtime on capacitated machinesProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627827(129-143)Online publication date: 6-Jan-2013
  • (2013)Competitive online algorithms for multiple-machine power management and weighted flow timeProceedings of the Nineteenth Computing: The Australasian Theory Symposium - Volume 14110.5555/2525519.2525521(11-20)Online publication date: 29-Jan-2013
  • (2013)Speed Scaling with an Arbitrary Power FunctionACM Transactions on Algorithms10.1145/2438645.24386509:2(1-14)Online publication date: 1-Mar-2013
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media