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. © H.L. Chan, J. Edmonds, T.WL. am, L.K. Lee, A. Marchetti-Spaccamela, and K. Pruhs.
Nonclairvoyant Speed Scaling for Flow and Energy / HO LEUNG, Chan; Jeff, Edmonds; TAK WAH, Lam; LAP KEI, Lee; MARCHETTI SPACCAMELA, Alberto; Kirk, Pruhs. - 3:(2009), pp. 255-264. (Intervento presentato al convegno 26th International Symposium on Theoretical Aspects of Computer Science, tenutosi a Freiburg; Germany nel 26-28, febbraio, 2009) [10.4230/LIPIcs.STACS.2009.1815].
Nonclairvoyant Speed Scaling for Flow and Energy
MARCHETTI SPACCAMELA, Alberto;
2009
Abstract
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. © H.L. Chan, J. Edmonds, T.WL. am, L.K. Lee, A. Marchetti-Spaccamela, and K. Pruhs.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2009_11573-215184.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
412.11 kB
Formato
Adobe PDF
|
412.11 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
