On the performance of greedy algorithms for energy minimization

Anne Benoit 1 Paul Renaud-Goud 1 Yves Robert 1
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Nous revisitons l'algorithme glouton bien connu d'ordonnancement de travaux indépendants sur des processeurs parallèles, avec un nouvel objectif de minimisation d'énergie. Nous étudions les performances de la version "online" et de la version "offline", cette dernière triant les travaux par ordre croissant de taille avant l'exécution. Nous donnons de nouveaux facteurs d'approximation, ainsi que des exemples qui montrent que ces facteurs ne peuvent pas être améliorés. Nous caractérisons donc complètement les performances de ces algorithmes.
Type de document :
Rapport
[Research Report] RR-LIP-2010-27, 2010, pp.12
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00515209
Contributeur : Paul Renaud-Goud <>
Soumis le : jeudi 13 octobre 2011 - 10:37:36
Dernière modification le : vendredi 20 avril 2018 - 15:44:23
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 04:52:24

Fichier

RR-2010-27.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00515209, version 2

Collections

Citation

Anne Benoit, Paul Renaud-Goud, Yves Robert. On the performance of greedy algorithms for energy minimization. [Research Report] RR-LIP-2010-27, 2010, pp.12. 〈inria-00515209v2〉

Partager

Métriques

Consultations de la notice

205

Téléchargements de fichiers

90