mlsanityData to 7 Oct 2026

Online Algorithms for Weighted Paging with Predictions

arXiv 2006.09509 ↗First posted 16 Jun 2020cs.DScited by 29

Not on the map. Why?

Abstract (arXiv)

In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor knowledge of the next request for every page is sufficient information for an algorithm to overcome existing lower bounds in weighted paging. However, a combination of the two, which we call the strong per request prediction (SPRP) model, suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

29 papers.

Sort:

  1. 2021Faster Matchings via Learned Dualscited by 56
  2. 2022Learning Predictions for Algorithms with Predictionscited by 25
  3. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  4. 2022Online Algorithms with Multiple Predictionscited by 22
  5. 2022Customizing ML Predictions for Online Algorithmscited by 21
  6. 2022Parsimonious Learning-Augmented Cachingcited by 19
  7. 2022Algorithms with Prediction Portfolioscited by 19
  8. 2022A Regression Approach to Learning-Augmented Online Algorithmscited by 12
  9. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  10. 2021(Optimal) Online Bipartite Matching with Degree Informationcited by 11
  11. 2021Logarithmic Regret from Sublinear Hintscited by 11
  12. 2021Double Coverage with Machine-Learned Advicecited by 10
17 more
  1. 2022Paging with Succinct Predictionscited by 10
  2. 2021Learning-Augmented Algorithms for Online Steiner Treecited by 6
  3. 2022Learning-Augmented Private Algorithms for Multiple Quantile Releasecited by 5
  4. 2023Online Dynamic Acknowledgement with Learned Predictionscited by 4
  5. 2023The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformationscited by 4
  6. 2021Sequential Ski Rental Problemcited by 3
  7. 2025Incremental Approximate Single-Source Shortest Paths with Predictionscited by 3
  8. 2025Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistencycited by 3
  9. 2023On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rentalcited by 2
  10. 2024Online Learning with Sublinear Best-Action Queriescited by 2
  11. 2022Online TSP with Predictionscited by 1
  12. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  13. 2025Prediction-Augmented Mechanism Design for Weighted Facility Locationcited by 0
  14. 2026SCaLE: Switching Cost aware Learning and Explorationcited by 0
  15. 2026Online Algorithms with Unreliable Guidancecited by 0
  16. 2026Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Managementcited by 0
  17. 2026Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implicationscited by 0