Learning-Augmented Algorithms for Online TSP on the Line

We study the online Traveling Salesman Problem (TSP) on the line augmentedwith machine-learned predictions. In the classical problem, there is a streamof requests released over time along the real line. The goal is to minimize themakespan of the algorithm. We distinguish between the open variant and theclosed one, in which we additionally require the algorithm to return to theorigin after serving all requests. The state of the art is a $1.64$-competitivealgorithm and a $2.04$-competitive algorithm for the closed and open variants,respectively \cite{Bjelde:1.64}. In both cases, a tight lower bound is known\cite{Ausiello:1.75, Bjelde:1.64}. In both variants, our primary prediction model involves predicted positionsof the requests. We introduce algorithms that (i) obtain a tight 1.5competitive ratio for the closed variant and a 1.66 competitive ratio for theopen variant in the case of perfect predictions, (ii) are robust againstunbounded prediction error, and (iii) are smooth, i.e., their performancedegrades gracefully as the prediction error increases. Moreover, we further investigate the learning-augmented setting in the openvariant by additionally considering a prediction for the last request served bythe optimal offline algorithm. Our algorithm for this enhanced setting obtainsa 1.33 competitive ratio with perfect predictions while also being smooth androbust, beating the lower bound of 1.44 we show for our original predictionsetting for the open variant. Also, we provide a lower bound of 1.25 for thisenhanced setting.