Learning-Augmented Online TRP on a Line

• URL: http://arxiv.org/abs/2601.13494v1
• Date: Tue, 20 Jan 2026 01:10:02 GMT
• Title: Learning-Augmented Online TRP on a Line
• Abstract summary: We study the online traveling repairperson problem on a line within the recently proposed learning-augmented framework.<n>Our prediction model involves predicted positions, possibly error-prone, of each request in the stream known a priori.<n>We show that our deterministic algorithm becomes $min3.732+4,4$-competitive, knowing $$.
• Score: 0.7677431882779153
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the online traveling repairperson problem on a line within the recently proposed learning-augmented framework, which provides predictions on the requests to be served via machine learning. In the original model (with no predictions), there is a stream of requests released over time along the line. The goal is to minimize the sum (or average) of the completion times of the requests. In the original model, the state-of-the-art competitive ratio lower bound is $1+\sqrt{2} > 2.414$ for any deterministic algorithm and the state-of-the-art competitive ratio upper bound is 4 for a deterministic algorithm. Our prediction model involves predicted positions, possibly error-prone, of each request in the stream known a priori but the arrival times of requests are not known until their arrival. We first establish a 3-competitive lower bound which extends to the original model. We then design a deterministic algorithm that is $(2+\sqrt{3})\approx 3.732$-competitive when predictions are perfect. With imperfect predictions (maximum error $δ> 0$), we show that our deterministic algorithm becomes $\min\{3.732+4δ,4\}$-competitive, knowing $δ$. To the best of our knowledge, these are the first results for online traveling repairperson problem in the learning-augmented framework.

Related papers

• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  We study the problem of learning a drifting concept in the presence of Massart noise.<n>In this framework, an online learner has access to a history of independent samples.<n>The goal is to output, in each round, a hypothesis with small prediction error.
  arXiv  Detail & Related papers  (2026-06-09T17:35:18Z)
• Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model [16.466711636334587]
  Online decision-makers often obtain predictions on future variables, such as arrivals, demands, and so on. Prediction accuracy is unknown to decision-makers a priori, hence blindly following the predictions can be harmful. We develop algorithms that utilize predictions in a manner that is robust to the unknown prediction accuracy.
  arXiv  Detail & Related papers  (2024-02-21T04:57:32Z)
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions [19.537289123577022]
  We consider an online two-stage optimization with long-term constraints over a finite horizon of $T$ periods. We develop online algorithms for the online two-stage problem from adversarial learning algorithms.
  arXiv  Detail & Related papers  (2024-01-02T07:46:33Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of $T$ days (or times) The goal is to make a prediction with the minimum cost, specifically compared to the best expert in the set. We show a space lower bound of $widetildeOmegaleft(fracnMRTright)$ for any deterministic algorithm that achieves regret $R$ when the best expert makes $M$ mistakes.
  arXiv  Detail & Related papers  (2023-03-03T04:39:53Z)
• 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)
• Learning-Augmented Algorithms for Online TSP on the Line [4.636538620253008]
  We study the online Traveling Salesman Problem (TSP) on the line augmented with machine-learned predictions. In the classical problem, there is a stream of requests released over time along the real line. We distinguish between the open variant and the closed one, in which we additionally require the algorithm to return to the origin after serving all requests.
  arXiv  Detail & Related papers  (2022-06-01T17:47:26Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  We introduce a novel measure for quantifying the error in input predictions. The measure captures errors due to absent predicted requests as well as unpredicted actual requests.
  arXiv  Detail & Related papers  (2022-05-25T15:24:03Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  Online learning with expert advice is a fundamental problem of sequential prediction. The goal is to process predictions, and make a prediction with the minimum cost. An algorithm is judged by how well it does compared to the best expert in the set.
  arXiv  Detail & Related papers  (2022-04-21T01:22:18Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  We study the problem of online optimization, where a decision maker must choose points in a general metric space to the sum of per-round, non-competitive hitting costs and the costs of switching between rounds. We propose a novel algorithm, Adaptive Online Switching (AOS), and prove that, for any desired $delta 0)$competitive if predictions are perfect, it is $tildecalO(alphadelta)$ even when predictions are inaccurate.
  arXiv  Detail & Related papers  (2022-02-07T21:08:02Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  We show that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate. We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(log n)$ competitive.
  arXiv  Detail & Related papers  (2020-12-17T04:56:51Z)
• Online Page Migration with ML Advice [26.929268665630342]
  We consider online algorithms for the em page migration problem that use predictions, potentially imperfect, to improve their performance. We show that if the algorithm is given a prediction of the input sequence, then it can achieve a competitive ratio that tends to $1$. Our result adds to the recent body of work that uses machine learning to improve the performance of classic'' algorithms.
  arXiv  Detail & Related papers  (2020-06-09T03:15:34Z)

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.