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. The goal is to minimize the makespan of the algorithm. 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. The state of the art is a $1.64$-competitive algorithm 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 positions of the requests. We introduce algorithms that (i) obtain a tight 1.5 competitive ratio for the closed variant and a 1.66 competitive ratio for the open variant in the case of perfect predictions, (ii) are robust against unbounded prediction error, and (iii) are smooth, i.e., their performance degrades gracefully as the prediction error increases. Moreover, we further investigate the learning-augmented setting in the open variant by additionally considering a prediction for the last request served by the optimal offline algorithm. Our algorithm for this enhanced setting obtains a 1.33 competitive ratio with perfect predictions while also being smooth and robust, beating the lower bound of 1.44 we show for our original prediction setting for the open variant. Also, we provide a lower bound of 1.25 for this enhanced setting.
翻译:我们研究了线上的在线旅行销售商问题(TSP), 加上机学预测。 在古典问题中, 沿实线长期释放了一系列较紧的下限请求。 目标是将算法的构成范围最小化。 我们区分了开放变量和封闭变量。 在这两种变量中, 我们进一步要求算法在满足所有请求后返回源头。 艺术的状态是1.64美元竞争性算法和2.04美元对封闭变量和开放变量的竞争性算法, 分别为\cite{Bjelde:1.64}。 在这两种情况下, 都已知有一条较紧的较低约束范围的请求。 在这两种变量中, 我们的目标是将开放变量与封闭变量区分开端。 我们引入了这样的算法, (一) 为封闭变量获得近1.5的竞争性比率, 和为开放变量提供2.04美元的竞争性算法, 以及 (三) 这两种情况下, 都有一个较紧的下限的下限值, 也就是说, 他们的性递增的预算法是优度 。