On energy-efficient computations with advice

Hans Joachim Böckenhauer*, Richard Dobson, Sacha Krug, Kathleen Steinhöfel

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paper

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer-Verlag Berlin Heidelberg
Pages747-758
Number of pages12
Volume9198
ISBN (Print)9783319213972
DOIs
Publication statusPublished - 24 Jun 2015
Event21st International Conference on Computing and Combinatorics Conference, COCOON 2015 - Beijing, China
Duration: 4 Aug 20156 Aug 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9198
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference21st International Conference on Computing and Combinatorics Conference, COCOON 2015
Country/TerritoryChina
CityBeijing
Period4/08/20156/08/2015

Fingerprint

Dive into the research topics of 'On energy-efficient computations with advice'. Together they form a unique fingerprint.

Cite this