Improved bounds for speed scaling in devices obeying the cube-root rule

N. Bansal, H.L. Chan, D. Katz, K.R. Pruhs

Research output: Contribution to journalArticleAcademicpeer-review

237 Downloads (Pure)


Speed scaling is a power management technology that involves dynamically changing the speed of a processor. This technology gives rise to dual-objective scheduling problems, where the operating system both wants to conserve energy and optimize some Quality of Service (QoS) measure of the resulting schedule. In the most investigated speed scaling problem in the literature, the QoS constraint is deadline feasibility, and the objective is to minimize the energy used. The standard assumption is that the processor power is of the form s^a where s is the processor speed, and a>1 is some constant; a˜3 for CMOS based processors. In this paper we introduce and analyze a natural class of speed scaling algorithms, that we call qOA. The algorithm qOA sets the speed of the processor to be q times the speed that the optimal offline algorithm would run the jobs in the current state. When a=3, we show that qOA is 6.7-competitive, improving upon the previous best guarantee of 27 achieved by the algorithm Optimal Available (OA). We also give almost matching upper and lower bounds for qOA for general a. Finally, we give the first non-trivial lower bound, namely e^(a-1) / a, on the competitive ratio of a general deterministic online algorithm for this problem.
Original languageEnglish
Pages (from-to)209-229
Number of pages21
JournalTheory of Computing
Issue number9
Publication statusPublished - 2012


Dive into the research topics of 'Improved bounds for speed scaling in devices obeying the cube-root rule'. Together they form a unique fingerprint.

Cite this