loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
Optimal Power-Down Strategies
Rome, Italy
October 17-October 19
ISBN: 0-7695-2228-9
John Augustine, University of California at Irvine
Sandy Irani, University of California at Irvine
Chaitanya Swamy, Cornell University
We consider the problem of selecting threshold times to transition a device to low-power sleep states during an idle period. The two-state case in which there is a single active and a single sleep state is a continuous version of the ski-rental problem. We consider a generalized version in which there is more than one sleep state, each with its own power consumption rate and transition costs. We give an algorithm that, given a system, produces a deterministic strategy whose competitive ratio is arbitrarily close to optimal. We also give an algorithm to produce the optimal online strategy given a system and a probability distribution that generates the length of the idle period. We also give a simple algorithm that achieves a competitive ratio of 3 + 2\sqrt 2 \approx 5.828 for any system.
Citation:
John Augustine, Sandy Irani, Chaitanya Swamy, "Optimal Power-Down Strategies," focs, pp.530-539, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.