## 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 language | English |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Publisher | Springer-Verlag Berlin Heidelberg |

Pages | 747-758 |

Number of pages | 12 |

Volume | 9198 |

ISBN (Print) | 9783319213972 |

DOIs | |

Publication status | Published - 24 Jun 2015 |

Event | 21st International Conference on Computing and Combinatorics Conference, COCOON 2015 - Beijing, China Duration: 4 Aug 2015 → 6 Aug 2015 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9198 |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | 21st International Conference on Computing and Combinatorics Conference, COCOON 2015 |
---|---|

Country/Territory | China |

City | Beijing |

Period | 4/08/2015 → 6/08/2015 |