Learning-Augmented Online TRP on a Line
Swapnil Guragain, Gokarna Sharma · 2026
Read Learning-Augmented Online TRP on a Line by Swapnil Guragain, Gokarna Sharma (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-13494.txt.
Introduction
Swapnil Guragain and Gokarna Sharma study an on line repair route task where a learner gives hints. In the task, calls land over time on a line. A repair worker must serve each call. The aim is low wait. In the classic form no hints are given, and calls are a surprise as they land.
In the learnt form, a machine learner hints where calls will land. A good rule uses hints when they help and guards when they err. The team builds such rules for the line case. For service fleets, hint led routes can cut wait if the hint trust is set with care.
Catalog record
| CREATOR | Swapnil Guragain, Gokarna Sharma |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-13494
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning-Augmented Online TRP on a Line Swapnil Guragain, Gokarna Sharma 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 + 2 > 2.414 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 + 3 ) ≈ 3.732 (2+\sqrt{3})\approx 3.732 -competitive when predictions are perfect. With imperfect predictions (maximum error δ > 0 \delta>0 ), we show that our deterministic algorithm becomes min { 3.732 + 4 δ , 4 } \min\{3.732+4\delta,4\} -competitive, knowing δ \delta . To the best of our knowledge, these are the first results for online traveling repairperson problem in the learning-augmented framework. 1 Introduction We consider the online variant of the fundamental traveling repairperson problem (TRP). We solve online TRP on a real line \mathcal{L} of length |\mathcal{L}| . The input is a stream of requests released over time along the points on \mathcal{L} . The goal in TRP is to minimize the sum (or average) of the completion times of the requests, in contrast to traveling salesperson problem (TSP) where the goal is to minimize the maximum completion time (or makespan). TRP facilitates quickly serving each request rather than TSP which minimizes the maximum time to serve any request. TRP has a variety of relevant applications in logistics and robotics. Consider for an example a salesman/repairman/vehicle/robot (denoted as server in this paper) that has to serve locations on its workspace. If the server’s workspace is a road/highway segment, then it resembles a line and our results can apply to such application. The algorithm we design will run by the server to serve requests. Online TRP has been studied quite extensively on the original model where locations of the requests as well as their arrival times are not known until they arrive; we will define competitive ratio formally later. In this paper, we study online TRP considering a stronger prediction model within the recently proposed learning-augmented framework 10 ; 11 ; 9 (Table 1 compares original and prediction models). The prediction model provides some knowledge on problem beforehand through some external source as considered in the learning-augmented framework. The external source can be a machine learning approach running over the historical data relevant to the problem. Specifically, we consider the prediction model that involves predictions on the locations as considered in 6 where requests will arrive over time. Notice that in the original model (no predictions), no such knowledge is provided to the online algorithm ON . In our prediction model, ON is provided beforehand with the predicted locations of the future requests. Model Characteristic Original Requests arriving at time t are known at t Prediction All request locations are known beforehand but not time t the requests arrive Table 1: Comparing original and prediction models. Online TSP, where the goal is minimize the maximum completion time, has been studied on a line in the prediction model we discussed above 6 . However, to the best of our knowledge, there is no previous study on online TRP in the prediction model even on a line. This paper is the first attempt on online TRP in the prediction model on a line as in 6 . Paper Competitive Ratio Model 5 1+\sqrt{2}\approx 2.414 Original This paper 3 Original Table 2: Deterministic online TRP lower bounds on a line. Our Results. We have the following four results. We say that the prediction is perfect if the request predicted to arrive at a location actually arrives at that location. The prediction is called imperfect otherwise with parameter 0\leq\delta\leq 1 denoting the amount of prediction error. We say that line \mathcal{L} is a half-line if servers’ location is at its either end. • We establish that no deterministic algorithm can achieve 3 competitive ratio on a line in our prediction model even under perfect predictions. Interestingly, this lower bound applies to the original model since our prediction model makes the problem stronger. ( Section 3 ) • We develop a deterministic algorithm with a competitive ratio upper bound of 2+\sqrt{3}\approx 3.732 on a half-line in the original model. This bound extends to our prediction model with any prediction error 0\leq\delta\leq 1 . ( Section 4 ) • In our prediction model with perfect predictions, we develop a deterministic algorithm with competitive ratio 2+\sqrt{3}\approx 3.732 on a line. ( Section 5 ) • In our prediction model with imperfect predictions (error \delta>0 ), we give a deterministic \min\{3.732+4\delta,4\} -competitive algorithm, knowing \delta . ( Section 6 ) Tables 2 and 3 summarize the existing results in the original model as well as our results in the prediction model. Related Work. All existing results on online TRP are in the original model. 5 established the only previously known competitive lower bound of 1+\sqrt{2}\approx 2.414 for online TRP, which is the state-of-the-art. This lower bound applies to any metric that satisfies triangle inequality (line is a special case). We provide in this paper the improved competitive lower bound of 3 in a line (more precisely a half-line) which will also serve as a lower bound for any metric satisfying triangle inequality. Regarding the upper bound, 5 provided the first solution to online TRP on a line, which is a 9 -competitive deterministic algorithm. 8 obtained a (1+\sqrt{2})^{2}\approx 5.8285 in any metric which applies to line. 3 provided a 5.429 -competitive deterministic algorithm on a line. 7 give a 5.14 -competitive algorithm in any metric which applies to a line. The state-of-the-art is the 4-competitive deterministic algorithm in any metric due to 2 . 2 Model, Definitions, and Notations Model. We consider a single server initially located at a fixed distinguished location on \mathcal{L} , which we call origin o . The execution starts at time 0 and time proceeds in discrete time steps. The requests arrive at discrete time steps on any location on \mathcal{L} . Any number of requests may arrive at any time step. Each request is communicated to the server as soon as it arrives, i.e., a request r_{i} with arrival time t_{i} coming at some location p_{i} on \mathcal{L} is known by the server at time t_{i} . Server serves requests traversing \mathcal{L} starting from origin o . Request r_{i} is considered served when the server reaches the location p_{i} the first time while traversing \mathcal{L} . If server reaches p_{i} the first time at time t_{i}^{\prime} , then t_{i}^{\prime} is the completion time for r_{i} . Performance Metric – Sum of Completion Times. We consider n\geq 1 requests