Document detail
ID
oai:arXiv.org:2410.15257
Topic
Computer Science - Machine Learnin... Computer Science - Data Structures... Mathematics - Optimization and Con...Author
Zhao, Hailiang Tang, Xueyan Chen, Peng Deng, ShuiguangCategory
Computer Science
Year
2024
listing date
10/23/2024
Keywords
bahncard pfsum algorithm learning-augmentedAbstract
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.
;Comment: This paper has been accepted by the 38th Conference on Neural Information Processing Systems (NeurIPS 2024)
Zhao, Hailiang,Tang, Xueyan,Chen, Peng,Deng, Shuiguang, 2024, Learning-Augmented Algorithms for the Bahncard Problem
VR-Splatting: Foveated Radiance Field Rendering via 3D Gaussian Splatting and Neural Points
computer demands rendering neural
Attractor-Like Dynamics Extracted from Human Electrocorticographic Recordings Underlie Computational Principles of Auditory Bistable Perception
low-dimensional ecog subjects neural features dynamics perception
