# ICS 269, Spring 2004: Theory Seminar

## 23 April 2004:

Optimal Power-Down Strategies

John Augustine

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 5.828 for any
system.

From: Optimal Power-Down Strategies by John Augustine, Sandy Irani, and
Chaitanya Swamy. Submitted for publication.