mlsanityData to 14 Oct 2026

Learning-Augmented Algorithms for the Bahncard Problem

arXiv 2410.15257 ↗First posted 20 Oct 2024cs.LG cs.DS math.OCcited by 7

Not on the map. Why?

Abstract (arXiv)

In this paper, we study learning-augmented algorithms for the Bahncard problem. The Bahncard problem is a generalization of the ski-rental problem, where a traveler needs to irrevocably and repeatedly decide between a cheap short-term solution and an expensive long-term one with an unknown future. Even though the problem is canonical, only a primal-dual-based learning-augmented algorithm was explicitly designed for it. We develop a new learning-augmented algorithm, named PFSUM, that incorporates both history and short-term future to improve online decision making. We derive the competitive ratio of PFSUM as a function of the prediction error and conduct extensive experiments to show that PFSUM outperforms the primal-dual-based algorithm.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 13 of its 31 references that are in the map. First posted on arXiv 20 Oct 2024.

Builds on

13 of 31 references.

References · 13

  1. 2018Competitive caching with machine learned advicecited by 195
  2. 2020Algorithms with Predictionscited by 153
  3. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 80
  4. 2024Improving Online Algorithms via ML Predictionscited by 66
  5. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  6. 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
  7. 2022Learning Augmented Binary Search Treescited by 31
  8. 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
  9. 2022Online Algorithms with Multiple Predictionscited by 22
  10. 2022Customizing ML Predictions for Online Algorithmscited by 21
  11. 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
  12. 2024Learning-augmented Online Algorithm for Two-level Ski-rental Problemcited by 3
1 more
  1. 2013To Reserve or Not to Reserve: Optimal Online Multi-Instance Acquisition in IaaS Cloudscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 5.

7 papers.

  1. 2025Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistencycited by 3
  2. 2025Decision-Theoretic Approaches for Improved Learning-Augmented Algorithmscited by 0
  3. 2026Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratiocited by 0
  4. 2026Resilient Byzantine Agreement with Predictionscited by 0
  5. 2026Towards Optimal Robustness in Learning-Augmented Pagingcited by 0
  6. 2026Learning Augmented Exact Exponential Algorithmscited by 0
  7. 2026Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implicationscited by 0