# Learning-Augmented Algorithms for the Bahncard Problem

arXiv: https://arxiv.org/abs/2410.15257 · HTML: https://mlsanity.com/paper/2410.15257/

## 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 (most cited first, 13 of 13)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Learning-augmented Online Algorithm for Two-level Ski-rental Problem](https://mlsanity.com/paper/2402.06715/) (2024)
- [To Reserve or Not to Reserve: Optimal Online Multi-Instance Acquisition in IaaS Clouds](https://mlsanity.com/paper/1305.5608/) (2013)

## Built on by (most cited first, 7 of 7)

- [Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency](https://mlsanity.com/paper/2507.16242/) (2025)
- [Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.17701/) (2025)
- [Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio](https://mlsanity.com/paper/2601.06813/) (2026)
- [Resilient Byzantine Agreement with Predictions](https://mlsanity.com/paper/2605.19452/) (2026)
- [Towards Optimal Robustness in Learning-Augmented Paging](https://mlsanity.com/paper/2606.01342/) (2026)
- [Learning Augmented Exact Exponential Algorithms](https://mlsanity.com/paper/2606.18807/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## 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.