Nonclairvoyant Speed Scaling for Flow and Energy

Simple item page
dc.creatorChan, Ho-Leung
dc.creatorEdmonds, Jeff
dc.creatorLam, Tak-Wah
dc.creatorLee, Lap-Kei
dc.creatorMarchetti-Spaccamela, Alberto
dc.creatorPruhs, Kirk
dc.date2009-02-07
dc.date.accessioned2026-07-07T12:39:20Z
dc.date.available2026-07-07T12:39:20Z
dc.descriptionWe 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\^\propto. We give a nonclairvoyant algorithm that is shown to be O(\propto\^3)-competitive. We then show an Ω(\propto\^(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.
dc.identifierhttps://arxiv.org/abs/0902.1260
dc.identifierhttp://arxiv.org/abs/0902.1260
dc.identifier26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 255-264
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/219076
dc.subjectData Structures and Algorithms
dc.titleNonclairvoyant Speed Scaling for Flow and Energy
dc.typetext

Files

Collections

arXiv