论文标题
用于度量多个访问路径TSP的3/2 approximation
A 3/2-Approximation for the Metric Many-visits Path TSP
论文作者
论文摘要
在多个访问的路径TSP中，我们将为我们提供一组$ n $的城市及其成对距离（或成本）$ c（uv）$，此外，每个城市$ v $都带有相关的正整数请求$ r（v）$。 目标是找到一条最低成本的路径，从城市$ s $开始，并以城市$ t $结束，访问每个城市$ v $ $ r（v）$ times。 我们提出了一种$ \ frac32 $ -Approximation算法，用于公制多个访问tsp，该算法在$ n $中以$ n $和poly-logarithmic在请求$ r（v）$中运行。 我们的算法可以看作是对Zenklusen的Path TSP的$ \ frac32 $ -Approximation算法的深远概括（Soda 2019），该算法通过提供有效的算法来回答一个长期的开放问题，该算法与Christofides of Christofides of Christofides of 1976 for Metrric Tsp的近似保证相匹配。 我们方法的关键组成部分之一是一种多项式时间算法，用于计算最低成本的连接的，度界的多式图。 我们通过概括了基拉利，劳和辛格（Combinatorica，2012）对最小有限程度的矩阵基础问题的基本结果来解决这个问题，并为一般多膜质的算法设计了这种算法，甚至允许元素多重性。 我们的结果直接产生了$ \ frac32 $ - approximation，以备值tsp，以及$ \ frac32 $ - approximation，以在单个计算机上安排依赖序列设置时间的作业的问题，以最大程度地减少制造商。
In the Many-visits Path TSP, we are given a set of $n$ cities along with their pairwise distances (or cost) $c(uv)$, and moreover each city $v$ comes with an associated positive integer request $r(v)$. The goal is to find a minimum-cost path, starting at city $s$ and ending at city $t$, that visits each city $v$ exactly $r(v)$ times. We present a $\frac32$-approximation algorithm for the metric Many-visits Path TSP, that runs in time polynomial in $n$ and poly-logarithmic in the requests $r(v)$. Our algorithm can be seen as a far-reaching generalization of the $\frac32$-approximation algorithm for Path TSP by Zenklusen (SODA 2019), which answered a long-standing open problem by providing an efficient algorithm which matches the approximation guarantee of Christofides' algorithm from 1976 for metric TSP. One of the key components of our approach is a polynomial-time algorithm to compute a connected, degree bounded multigraph of minimum cost. We tackle this problem by generalizing a fundamental result of Király, Lau and Singh (Combinatorica, 2012) on the Minimum Bounded Degree Matroid Basis problem, and devise such an algorithm for general polymatroids, even allowing element multiplicities. Our result directly yields a $\frac32$-approximation to the metric Many-visits TSP, as well as a $\frac32$-approximation for the problem of scheduling classes of jobs with sequence-dependent setup times on a single machine so as to minimize the makespan.
