caa a22 4500 445805188 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00453-010-9420-2 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9420-2 Nonclairvoyant Speed Scaling for Flow and Energy [Elektronische Daten] [Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, Kirk Pruhs] 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 $\frac{2\alpha^{2}}{\ln\alpha}$ for α>3. We then show that there is no constantc, and no deterministic nonclairvoyant algorithmA, 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. The Author(s), 2010 Speed scaling nationallicence Power management nationallicence Online scheduling nationallicence Competitive analysis nationallicence Chan Ho-Leung The University of Hong Kong, Hong Kong, Hong Kong aut Edmonds Jeff York University, M3J 1P3, Toronto, Ontario, Canada aut Lam Tak-Wah The University of Hong Kong, Hong Kong, Hong Kong aut Lee Lap-Kei Max-Planck-Institut für Informatik, 66123, Saarbrücken, Germany aut Marchetti-Spaccamela Alberto Dipartimento di Informatica e Sistemistica, Sapienza Università di Roma, 00185, Roma, Italy aut Pruhs Kirk University of Pittsburgh, 15260, Pittsburgh, PA, USA aut Algorithmica Springer-Verlag 61/3(2011-11-01), 507-517 0178-4617 61:3<507 2011 61 453 https://doi.org/10.1007/s00453-010-9420-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9420-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Chan Ho-Leung The University of Hong Kong, Hong Kong, Hong Kong aut NATIONALLICENCE 700 1- Edmonds Jeff York University, M3J 1P3, Toronto, Ontario, Canada aut NATIONALLICENCE 700 1- Lam Tak-Wah The University of Hong Kong, Hong Kong, Hong Kong aut NATIONALLICENCE 700 1- Lee Lap-Kei Max-Planck-Institut für Informatik, 66123, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Marchetti-Spaccamela Alberto Dipartimento di Informatica e Sistemistica, Sapienza Università di Roma, 00185, Roma, Italy aut NATIONALLICENCE 700 1- Pruhs Kirk University of Pittsburgh, 15260, Pittsburgh, PA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/3(2011-11-01), 507-517 0178-4617 61:3<507 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer