Learning-Augmented Algorithms for the Bahncard Problem

• URL: http://arxiv.org/abs/2410.15257v1
• Date: Sun, 20 Oct 2024 02:55:15 GMT
• Title: Learning-Augmented Algorithms for the Bahncard Problem
• Authors: Hailiang Zhao, Xueyan Tang, Peng Chen, Shuiguang Deng,
• Abstract summary: We study learning-augmented algorithms for the Bahncard problem. PFSUM incorporates both history and short-term future to improve online decision making.
• Score: 12.852098444482426
• License:
• 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.

Related papers

• On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental [0.0]
  A learning-augmented multi-option ski rental problem generalizes the classical ski rental problem in two ways. For randomized algorithms, we show the first nontrivial lower bound on the consistency-robustness trade-off. Our algorithm matches our lower bound on robustness within a factor of e/2 when the consistency is at most 1.086.
  arXiv  Detail & Related papers  (2023-12-05T07:33:51Z)
• Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis [0.1529342790344802]
  We present improved learning-augmented algorithms for the multi-option ski rental problem. Our algorithm is based on a new, provably best-possible randomized competitive algorithm for the problem.
  arXiv  Detail & Related papers  (2023-02-14T05:05:03Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  We consider non-clairvoyant scheduling with online precedence constraints. An algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed.
  arXiv  Detail & Related papers  (2023-01-30T13:17:15Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds [38.80523710193321]
  We study the online problem of minimizing power consumption in systems with multiple power-saving states. An algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We develop a learning-augmented online algorithm that makes decisions based on (potentially inaccurate) predicted lengths of the idle periods.
  arXiv  Detail & Related papers  (2021-10-25T17:14:20Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Robust Learning-Augmented Caching: An Experimental Study [8.962235853317996]
  Key optimization problem arising in caching cannot be optimally solved without knowing the future. New field of learning-augmented algorithms proposes solutions that leverage classical online caching algorithms. We show that a straightforward method has only a low overhead over a well-performing predictor.
  arXiv  Detail & Related papers  (2021-06-28T13:15:07Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.