Theory of Computing ------------------- Title : Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule Authors : Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, and Kirk Pruhs Volume : 8 Number : 9 Pages : 209-229 URL : https://theoryofcomputing.org/articles/v008a009 Abstract -------- 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^alpha where s is the processor speed, and alpha > 1 is some constant; alpha \approx 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 alpha=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 alpha. Finally, we give the first non-trivial lower bound, namely e^{alpha-1}/alpha, on the competitive ratio of a general deterministic online algorithm for this problem.