Getting the best response for your erg

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

21 Citations (Scopus)


We consider the bi-criteria problem of minimizing the average flow time (average response time) of a collection of dynamically released equi-work processes subject to the constraint that a fixed amount of energy is available. We assume that the processor has the ability to dynamically scale the speed at which it runs, as do current microprocessors from AMD, Intel, and Transmeta. We first reveal the combinatorial structure of the optimal schedule. We then use these insights to devise a relatively simple polynomial time algorithm to simultaneously compute, for each possible energy, the schedule with optimal average flow time subject to this energy constraint.
Original languageEnglish
Title of host publicationAlgorithm theory - SWAT 2004 : 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8 - 10, 2004 ; proceedings
EditorsT. Hagerup, J. Katajainen
Place of PublicationBerlin
ISBN (Print)978-3-540-22339-9
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


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

Cite this