TY - GEN
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
PY - 2009
Y1 - 2009
N2 - We study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is P(s) = sα. We give a nonclairvoyant algorithm that is shown to be O(α3)-competitive. We then show an Ω(α 1/3-∈) lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be O(1)-competitive.
AB - We study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is P(s) = sα. We give a nonclairvoyant algorithm that is shown to be O(α3)-competitive. We then show an Ω(α 1/3-∈) lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be O(1)-competitive.
UR - https://www.scopus.com/pages/publications/84880233025
U2 - 10.4230/LIPIcs.STACS.2009.1815
DO - 10.4230/LIPIcs.STACS.2009.1815
M3 - Conference contribution
AN - SCOPUS:84880233025
SN - 9783939897095
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 255
EP - 264
BT - STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science
T2 - 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009
Y2 - 26 February 2009 through 28 February 2009
ER -