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α . 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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.255-264, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359287
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 14:47:46
Dernière modification le : jeudi 20 septembre 2018 - 07:54:02
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:00:25

Fichiers

HoLeungCHAN_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359287, version 1
  • ARXIV : 0902.1260

Collections

Citation

Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, et al.. Nonclairvoyant Speed Scaling for Flow and Energy. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.255-264, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359287〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

227