TY - CHAP
T1 - On energy-efficient computations with advice
AU - Böckenhauer, Hans Joachim
AU - Dobson, Richard
AU - Krug, Sacha
AU - Steinhöfel, Kathleen
PY - 2015/6/24
Y1 - 2015/6/24
N2 - 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 e/(e-1) with an increasing number of advice bits. For competitive ratios in the range [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), where w is the wake-up energy, needs to read a linear number of advice bits.
AB - 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 e/(e-1) with an increasing number of advice bits. For competitive ratios in the range [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), where w is the wake-up energy, needs to read a linear number of advice bits.
UR - http://www.scopus.com/inward/record.url?scp=84951003489&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-21398-9_58
DO - 10.1007/978-3-319-21398-9_58
M3 - Conference paper
AN - SCOPUS:84951003489
SN - 9783319213972
VL - 9198
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 747
EP - 758
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PB - Springer-Verlag Berlin Heidelberg
T2 - 21st International Conference on Computing and Combinatorics Conference, COCOON 2015
Y2 - 4 August 2015 through 6 August 2015
ER -