English

# 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 (), 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.