论文标题
在线学习算法的学习算法
Learning-Augmented Algorithms for Online TSP on the Line
论文作者
论文摘要
我们研究了在线旅行推销员问题（TSP），并通过机器学习的预测进行了增强。在经典问题中，随着时间的推移会沿真实行发布的一系列请求流。目的是最大程度地减少算法的制造物。我们区分开放式变体和封闭变体，其中还要求算法在服务所有请求后返回到原点。艺术状态分别为$ 1.64 $竞争算法和$ 2.04 $ - 竞争算法的封闭式和开放式变体，分别为\ cite {bjelde {bjelde：1.64}。在这两种情况下，都知道一个紧密的下限\ cite {ausiello：1.75，bjelde：1.64}。 在这两个变体中，我们的主要预测模型都涉及请求的预测位置。我们介绍了（i）在完美预测的情况下，（i）获得闭合变体的1.5竞争比和1.66的竞争比率，（ii）对未结合的预测误差具有鲁棒性，并且（iii）平稳，即，由于预测误差的增加，其性能优美地降级。 此外，我们还考虑了最佳离线算法对最后一个请求的预测，进一步研究了开放式变体中的学习效果。我们的此增强设置的算法获得了1.33的竞争比率，具有完美的预测，同时也保持光滑和强大，超过了1.44的下限，我们为开放变体的原始预测设置显示了。另外，我们为此增强设置提供了1.25的下限。
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.
