# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Speed Scaling with an Arbitrary Power Function

##### 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.