Speed Scaling with an Arbitrary Power Function
Nikhil Bansal, Ho-Leung Chan, Kirk R. Pruhs · Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms · 2009
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α, where α > 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+∊)-competitive algorithm for this problem, that holds for essentially any power function. We also give a (2 + ∊)-competitive algorithm for the objective of fractional weighted flow plus energy. Even for power functions of the form sα, it was not previously known how to obtain competitiveness independent of α for these problems. We also introduce a model of allowable speeds that generalizes all known models in the literature.