用历史与短期未来预测优化火车票购买决策，提升在线算法表现。
Learning-Augmented Algorithms for the Bahncard Problem
- 结合历史数据与短期未来预测，改进在线决策策略
- 理论证明性能随预测误差减小而提升，实验优于传统方法
- 适合需反复做长期/短期选择的场景，如订阅、采购
本文研究学习增强型算法在巴恩卡德问题中的应用。该问题为滑雪租赁问题的推广，旅行者需反复在廉价短期方案与昂贵长期方案间做出不可撤销决策，未来情况未知。尽管问题具有代表性，但此前仅有一种基于对偶的学習增强算法被明确提出。本文提出一种新算法PFSUM，融合历史信息与短期未来预测以优化在线决策。我们推导出PFSUM的竞争比作为预测误差的函数，并通过大量实验验证其性能优于对偶基算法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。