mlsanityData to 14 Oct 2026

Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds

arXiv 2110.13116 ↗First posted 25 Oct 2021cs.DS cs.LGcited by 20

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 20 papers in the map (data through 14 Oct 2026). Builds on 16 of its 49 references that are in the map. First posted on arXiv 25 Oct 2021.

Builds on

16 of 49 references.

References · 16

  1. 2018Competitive caching with machine learned advicecited by 195
  2. 2020Algorithms with Predictionscited by 153
  3. 2020Online metric algorithms with untrusted predictionscited by 75
  4. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  5. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  6. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  7. 2013Dynamical Models and Tracking Regret in Online Convex Programmingcited by 43
  8. 2019Online Computation with Untrusted Advicecited by 42
  9. 2020Secretaries with Advicecited by 41
  10. 2020Better and Simpler Learning-Augmented Online Cachingcited by 38
  11. 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
  12. 2018Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descentcited by 33
4 more
  1. 2021Double Coverage with Machine-Learned Advicecited by 10
  2. 2018Optimal Algorithms for Right-Sizing Data Centers- Extended Versioncited by 6
  3. 2016Energy-Efficient Algorithmscited by 4
  4. 2019Parallel Machine Scheduling to Minimize Energy Consumptioncited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 2; 2024: 5; 2025: 5; 2026: 6.

20 papers.

Sort:

  1. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  2. 2023Sorting with Predictionscited by 14
  3. 2023Mixing predictions for online metric algorithmscited by 13
  4. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  5. 2022Paging with Succinct Predictionscited by 10
  6. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  7. 2024Learning-Augmented Priority Queuescited by 7
  8. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  9. 2024Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problemscited by 5
  10. 2024Learning-augmented Online Algorithm for Two-level Ski-rental Problemcited by 3
  11. 2025Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistencycited by 3
  12. 2025Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictorscited by 2
8 more
  1. 2026Ski Rental with Distributional Predictions of Unknown Qualitycited by 2
  2. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  3. 2025Decision-Theoretic Approaches for Improved Learning-Augmented Algorithmscited by 0
  4. 2025Prediction-Specific Design of Learning-Augmented Algorithmscited by 0
  5. 2026Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratiocited by 0
  6. 2026Towards Optimal Robustness in Learning-Augmented Pagingcited by 0
  7. 2026Learning Augmented Exact Exponential Algorithmscited by 0
  8. 2026Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implicationscited by 0