License: 
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1815
URN: urn:nbn:de:0030-drops-18151
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1815/
Chan, Ho-Leung ;
Edmonds, Jeff ;
Lam, Tak-Wah ;
Lee, Lap-Kei ;
Marchetti-Spaccamela, Alberto ;
Pruhs, Kirk
Nonclairvoyant Speed Scaling for Flow and Energy
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^\alpha$. We give a nonclairvoyant algorithm that is shown to be $O(\alpha^3)$-competitive. We then show an $\Omega( \alpha^{1/3-\epsilon} )$ 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.
BibTeX - Entry
@InProceedings{chan_et_al:LIPIcs:2009:1815,
author = {Ho-Leung Chan and Jeff Edmonds and Tak-Wah Lam and Lap-Kei Lee and Alberto Marchetti-Spaccamela and Kirk Pruhs},
title = {{Nonclairvoyant Speed Scaling for Flow and Energy}},
booktitle = {26th International Symposium on Theoretical Aspects of Computer Science},
pages = {255--264},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-09-5},
ISSN = {1868-8969},
year = {2009},
volume = {3},
editor = {Susanne Albers and Jean-Yves Marion},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1815},
URN = {urn:nbn:de:0030-drops-18151},
doi = {10.4230/LIPIcs.STACS.2009.1815},
annote = {Keywords: }
}
|
Collection: |
|
26th International Symposium on Theoretical Aspects of Computer Science |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
19.02.2009 |
