Learning-Augmented Algorithms for the Bahncard Problem

Abstract

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.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Zhao et al. "Learning-Augmented Algorithms for the Bahncard Problem." Neural Information Processing Systems, 2024. doi:10.52202/079017-3598

Markdown

[Zhao et al. "Learning-Augmented Algorithms for the Bahncard Problem." Neural Information Processing Systems, 2024.](https://mlanthology.org/neurips/2024/zhao2024neurips-learningaugmented/) doi:10.52202/079017-3598

BibTeX

@inproceedings{zhao2024neurips-learningaugmented,
  title     = {{Learning-Augmented Algorithms for the Bahncard Problem}},
  author    = {Zhao, Hailiang and Tang, Xueyan and Chen, Peng and Deng, Shuiguang},
  booktitle = {Neural Information Processing Systems},
  year      = {2024},
  doi       = {10.52202/079017-3598},
  url       = {https://mlanthology.org/neurips/2024/zhao2024neurips-learningaugmented/}
}