Document Open Access Logo

Nonclairvoyant Speed Scaling for Flow and Energy

Authors Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, Kirk Pruhs

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2009.1815.pdf
  • Filesize: 167 kB
  • 10 pages

Document Identifiers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, and Kirk Pruhs. Nonclairvoyant Speed Scaling for Flow and Energy. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 255-264, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1815

Author Details

Ho-Leung Chan
Jeff Edmonds
Tak-Wah Lam
Lap-Kei Lee
Alberto Marchetti-Spaccamela
Kirk Pruhs
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact