Nikhil Bansal, Rohit Khandekar, et al.
SIAM Journal on Computing
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 a for these problems. We also introduce a model of allowable speeds that generalizes all known models in the literature. Copyright © by SIAM.
Nikhil Bansal, Rohit Khandekar, et al.
SIAM Journal on Computing
Nikhil Bansal, Zachary Friggstad, et al.
ACM Transactions on Algorithms
Nikhil Bansal, Moshe Lewenstein, et al.
Algorithmica (New York)
Nikhil Bansal, Ho-Leung Chan, et al.
Theoretical Computer Science