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 metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00515209
Contributor : Paul Renaud-Goud <>
Submitted on : Thursday, October 13, 2011 - 10:37:36 AM
Last modification on : Friday, April 20, 2018 - 3:44:23 PM
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

221

Files downloads

102