English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Speed Scaling with an Arbitrary Power Function

MPS-Authors
/persons/resource/persons44228

Chan,  Ho-Leung
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Bansal, N., Chan, H.-L., & Pruhs, K. (2009). Speed Scaling with an Arbitrary Power Function. In C. Mathieu (Ed.), Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 693-701). Philadelphia, PA: SIAM.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-18D3-F
Abstract
All of the theoretical speed scaling research to date has assumed that the power function, which expresses the power consumption $P$ as a function of the processor speed $s$, is of the form $P=s^\alpha$, where $\alpha > 1$ is some constant. Motivated in part by technological advances, we initiate a study of speed scaling with arbitrary power functions. We consider the problem of minimizing the total flow plus energy. Our main result is a $(3+\epsilon)$-competitive algorithm for this problem, that holds for essentially any power function. We also give a $(2+\epsilon)$-competitive algorithm for the objective of fractional weighted flow plus energy. Even for power functions of the form $s^\alpha$, it was not previously known how to obtain competitiveness independent of $\alpha$ for these problems. We also introduce a model of allowable speeds that generalizes all known models in the literature.