TY - JOUR

T1 - Nonclairvoyant speed scaling for flow and energy

AU - Chan, Ho Leung

AU - Edmonds, Jeff

AU - Lam, Tak Wah

AU - Lee, Lap Kei

AU - Marchetti-Spaccamela, Alberto

AU - Pruhs, Kirk

N1 - Funding Information:
This work of H.L. Chan was done when he was a postdoc in University of Pittsburgh. T.W. Lam is partially supported by HKU Grant 7176104. J. Edmonds supported in part by NSERC Canada. A. Marchetti-Spaccamela supported in part by MIUR FIRB grant RBIN047MH9 and by EU ICT-FET grant 215270 FRONTS. K. Pruhs supported in part by an IBM faculty award, and by NSF grants CNS-0325353, CCF-0514058, IIS-0534531, and CCF-0830558.

PY - 2011/11

Y1 - 2011/11

N2 - 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.

AB - 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.

KW - Competitive analysis

KW - Online scheduling

KW - Power management

KW - Speed scaling

UR - http://www.scopus.com/inward/record.url?scp=80052860798&partnerID=8YFLogxK

U2 - 10.1007/s00453-010-9420-2

DO - 10.1007/s00453-010-9420-2

M3 - Article

AN - SCOPUS:80052860798

SN - 0178-4617

VL - 61

SP - 507

EP - 517

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -