Optimal Power-Down Strategies
- Creators
- Augustine, John
- Irani, Sandy
- Swamy, Chaitanya
Abstract
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.
Additional Information
©2008 Society for Industrial and Applied Mathematics. Received by the editors August 10, 2005; accepted for publication (in revised form) October 10, 2007; published electronically January 30, 2008. This author's [J.A.] research was supported partially by NSF grants CCR-0105498 and CCF-0514082 and by ONR Award N00014-00-1-0617. This author's [S.I.] research was supported partially by NSF grants CCR-0105498 and CCF-0514082 and by ONR Award N00014-00-1-0617. This author's [C.S.] research was supported partially by NSF grant CCR-9912422.Files
Name | Size | Download all |
---|---|---|
md5:09f3e2922a7b4db0459803c11d7fb7d0
|
230.3 kB | Preview Download |
Additional details
- Eprint ID
- 10099
- Resolver ID
- CaltechAUTHORS:AUGsiamjc08
- Created
-
2008-04-13Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field