Getting the best response for your erg

K.R. Pruhs, P. Uthaisombut, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

70 Citations (Scopus)


We consider the speed scaling problem of minimizing the average response time of a collection of dynamically released jobs subject to a constraint A on energy used. We propose an algorithmic approach in which an energy optimal schedule is computed for a huge A, and then the energy optimal schedule is maintained as A decreases. We show that this approach yields an efficient algorithm for equi-work jobs. We note that the energy optimal schedule has the surprising feature that the job speeds are not monotone functions of the available energy. We then explain why this algorithmic approach is problematic for arbitrary work jobs. Finally, we explain how to use the algorithm for equi-work jobs to obtain an algorithm for arbitrary work jobs that is O(1)-approximate with respect to average response time, given an additional factor of (1 + ε) energy.
Original languageEnglish
Article number38
Pages (from-to)38-1/17
Number of pages17
JournalACM Transactions on Algorithms
Issue number3
Publication statusPublished - 2008


Dive into the research topics of 'Getting the best response for your erg'. Together they form a unique fingerprint.

Cite this