On Energy-Efficient Computations With Advice

Online problems have always played an important role in computer science. Here, not the whole input is known at the beginning, but it is only revealed gradually. These problems frequently occur in practice, and therefore the performance of algorithms for such problems is of great theoretical and practical interest. One such online problem is energy management in electronic devices, e. g., smartphones. As such a device is usually not being used permanently, it is reasonable to change to a lower-energy state (like hibernation) after a certain idle time. Resuming from hibernation, however, also needs a certain amount of energy; therefore, hibernation should only happen if the idle period is long.

Advice complexity is a recent approach for measuring the information content of an online problem, i. e., the amount of knowledge about the future parts of the input that is necessary to compute a high-quality solution. The approach allows for a more fine-grained analysis of the hardness of online problems than the classical competitive analysis.

We analyze the advice complexity of this problem. For systems with two states, we construct an online algorithm with advice that is 1.8-competitive with one advice bit and 1.6-competitive with five advice bits, whereas every deterministic algorithm without advice is known to be no better than 2-competitive. Moreover, the algorithm’s competitive ratio converges fast towards

$$\text {e}/ (\text {e}- 1)$$

e

/

(

e

-

1

)

with an increasing number of advice bits. For competitive ratios in the range

$$[1, \text {e}/ (\text {e}- 1)]$$

[

1

,

e

/

(

e

-

1

)

]

, we present two complementary algorithms: one behaves optimally on a certain prefix, and the other falls asleep on the longest phases. Conversely, we show that every algorithm with a competitive ratio less than

$$1 + 1 / (4w + 2)$$

1

+

1

/

(

4

w

+

2

)

, where

w

is the wake-up energy, needs to read a linear number of advice bits.