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

https://hal.inria.fr/inria-00515209
Contributor : Paul Renaud-Goud <>
Submitted on : Monday, September 6, 2010 - 11:04:26 AM
Last modification on : Friday, April 20, 2018 - 3:44:23 PM
Long-term archiving on: Tuesday, October 23, 2012 - 3:35:48 PM

File

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

Identifiers

  • HAL Id : inria-00515209, version 1

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-00515209v1⟩

Share

Metrics

Record views

55

Files downloads

146