Timezone: »
We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We develop a learning-augmented online algorithm that makes decisions based on (potentially inaccurate) predicted lengths of the idle periods. The algorithm's performance is near-optimal when predictions are accurate and degrades gracefully with increasing prediction error, with a worst-case guarantee almost identical to the optimal classical online algorithm for the problem. A key ingredient in our approach is a new algorithm for the online ski-rental problem in the learning augmented setting with tight dependence on the prediction error. We support our theoretical findings with experiments.
Author Information
Antonios Antoniadis (University of Twente)
Christian Coester (Tel Aviv University)
Marek Elias (Università Bocconi)
Adam Polak (Swiss Federal Institute of Technology Lausanne)
Bertrand Simon (CNRS)
More from the Same Authors
-
2021 Poster: Nearly-Tight and Oblivious Algorithms for Explainable Clustering »
Buddhima Gamlath · Xinrui Jia · Adam Polak · Ola Svensson -
2020 Poster: Secretary and Online Matching Problems with Machine Learned Advice »
Antonios Antoniadis · Themis Gouleakis · Pieter Kleer · Pavel Kolev