Nonclairvoyant speed scaling for flow and energy

Ho Leung Chan, Jeff Edmonds, Tak Wah Lam, Lap Kei Lee, Alberto Marchetti-Spaccamela, Kirk Pruhs

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

We give three results related to online nonclairvoyant speed scaling to minimize total flow time plus energy. We give a nonclairvoyant algorithm LAPS, and show that for every power function of the form P(s)=s α, LAPS is O(1)-competitive; more precisely, the competitive ratio is 8 for α=2, 13 for α=3, and 2α 2 ln α for α>3. We then show that there is no constant c, and no deterministic nonclairvoyant algorithm A, such that A is c-competitive for every power function of the form P(s)=s α . So necessarily the achievable competitive ratio increases as the steepness of the power function increases. Finally we show that there is a fixed, very steep, power function for which no nonclairvoyant algorithm can be O(1)-competitive.

Original languageEnglish
Pages (from-to)507-517
Number of pages11
JournalAlgorithmica
Volume61
Issue number3
DOIs
Publication statusPublished - Nov 2011
Externally publishedYes

Keywords

  • Competitive analysis
  • Online scheduling
  • Power management
  • Speed scaling

Fingerprint

Dive into the research topics of 'Nonclairvoyant speed scaling for flow and energy'. Together they form a unique fingerprint.

Cite this