Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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
Abstract : We revisit the well-known greedy algorithm for scheduling independent jobs on parallel processors, with the objective of energy minimization. We assess the performance of the online version, as well as the performance of the offine version, which sorts the jobs by non-increasing size before execution. We derive new approximation factors, as well as examples that show that these factors cannot be improved, thereby completely characterizing the performance of the algorithms.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Paul Renaud-Goud Connect in order to contact the contributor
Submitted on : Thursday, October 13, 2011 - 10:37:36 AM
Last modification on : Wednesday, October 26, 2022 - 8:16:07 AM
Long-term archiving on: : Sunday, December 4, 2016 - 4:52:24 AM


Files produced by the author(s)


  • HAL Id : inria-00515209, version 2



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⟩



Record views


Files downloads