first study power-down mechanisms that conserve energy by transitioning a device into low-power standby or sleep modes. Then we address dynamic speed scaling in variable-speed processors. This relatively new technique saves energy by utilizing the full speed/frequency spectrum of a processor and applying low speeds whenever possible. Finally, we consider some optimization problems in wireless networks from an energy savings perspective.

We remark that all the above prob-
lems have also been studied in the
systems literature. The correspond-
ing papers also present algorithmic
approaches but usually do not prove
performance guarantees.

Power-Down mechanisms
Power-down mechanisms are well-
known and widely used techniques to
save energy. We encounter them on
an everyday basis. The display of our
desktop turns off after some period
of inactivity. Our laptop transitions
to a standby or hibernate mode if it
has been idle for a while. In these
settings, there usually exist idleness
thresholds that specify the length of
time after which a system is powered
down when not in use. The following
natural question arises: Is it possible
to design strategies that determine
such thresholds and always achieve
a provably good performance rela-
tive to the optimum solution? There
exists a rich literature on power-down
mechanisms, ranging from algorith-
mic to stochastic and learning-based
approaches. This article concentrates
on algorithmic solutions. We refer the
reader to Benini et al. and Irani et al. 14,
25 for surveys on other techniques.

 

Power management and competitiveness Problem setting: In a general scenario, we are given a device that always resides in one of several states. In