标题： 近似图多路径TSP和图有序TSP 显示英文标题

标题： Approximating Graphic Multi-Path TSP and Graphic Ordered TSP

摘要： 旅行商问题的路径版本是广泛研究的TSP最著名的变种之一。其推广形式，多路径TSP，最近被用于Traub和Vygen [剑桥大学出版社，2024] 的路径TSP最佳已知算法中。该问题的最佳已知近似因子为$2.214$，由Böhm、Friggstad、Mömke和Spoerhase [SODA 2025] 提出。在本文中，我们证明对于图形度量的情况，可以获得显著更好的近似保证，即$2$。我们的算法基于从对应于该问题线性规划最优解的流分解中采样路径，并用加倍的边连接被遗漏的顶点。后者成本在最坏情况下是最优值的两倍；我们展示了如何将采样路径的成本吸收进去而不增加近似因子。此外，我们证明，对于该问题的一个特殊情况，每个源点都与相应的汇点相同的情况下，任何低于$2$的近似算法都将产生一个低于$2$的近似算法用于图形多路径TSP。我们还表明，我们的想法可以用来给出有序TSP在图形度量下的因子$1.791$近似算法，对于该问题，上述论文 [SODA 2025] 和Armbruster、Mnich和Nägele [APPROX 2024] 在一般度量下给出了$1.868$近似算法。 显示英文摘要

摘要： The path version of the Traveling Salesman Problem is one of the most well-studied variants of the ubiquitous TSP. Its generalization, the Multi-Path TSP, has recently been used in the best known algorithm for path TSP by Traub and Vygen [Cambridge University Press, 2024]. The best known approximation factor for this problem is $2.214$ by B\"{o}hm, Friggstad, M\"{o}mke and Spoerhase [SODA 2025]. In this paper we show that for the case of graphic metrics, a significantly better approximation guarantee of $2$ can be attained. Our algorithm is based on sampling paths from a decomposition of the flow corresponding to the optimal solution to the LP for the problem, and connecting the left-out vertices with doubled edges. The cost of the latter is twice the optimum in the worst case; we show how the cost of the sampled paths can be absorbed into it without increasing the approximation factor. Furthermore, we prove that any below-$2$ approximation algorithm for the special case of the problem where each source is the same as the corresponding sink yields a below-$2$ approximation algorithm for Graphic Multi-Path TSP. We also show that our ideas can be utilized to give a factor $1.791$-approximation algorithm for Ordered TSP in graphic metrics, for which the aforementioned paper [SODA 2025] and Armbruster, Mnich and N\"agele [APPROX 2024] give a $1.868$-approximation algorithm in general metrics.