Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00515209
Contributor : Paul Renaud-Goud Connect in order to contact the contributor
Submitted on : Thursday, October 13, 2011 - 10:37:36 AM
Last modification on : Saturday, September 11, 2021 - 3:17:04 AM
Long-term archiving on: : Sunday, December 4, 2016 - 4:52:24 AM

File

RR-2010-27.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

276

Files downloads

254