论文标题
许多访问TSP重新审视
Many visits TSP revisited
论文作者
论文摘要
我们研究了许多访问TSP问题，其中$ n $ Cities和Pairwise（可能是不对称）整数距离都给出了数字$ k（v）$，人们必须找到一个最佳旅行，访问每个城市$ v $ v $ $ k（v）$ times。目前最快的算法归因于Berger，Kozma，Mnich和Vincze [Soda 2019，Talg 2020]，并在时空运行$ \ Mathcal {O}^*（5^n）$。他们还显示了随时间运行的多项式空间算法$ \ mathcal {o}^*（16^{n+o（n）}）$。 在这项工作中，我们显示了三个主要结果：（i）随机的随机多项式空间算法$ \ MATHCAL {O}^*（2^nd）$，其中$ d $是两个城市之间的最大距离。通过使用标准方法，这将导致$（1+ε）$ - 近似时间$ \ MATHCAL {O}^*（2^nε^{ - 1}）$。在这些结果中提高常数$ 2 $将是一个重大突破，因为这将改善$ \ Mathcal {O}^*（2^n）$ - 定向汉密尔顿周期的时间算法，这是一个50年的开放问题。 （ii）对Berger等人的指数空间算法的严格分析，导致$ \ MATHCAL {O}^*（4^n）$运行时间绑定。 （iii）一种新的多项式空间算法，在时间上运行$ \ mathcal {o}（7.88^n）$。
We study the Many Visits TSP problem, where given a number $k(v)$ for each of $n$ cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city $v$ exactly $k(v)$ times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space $\mathcal{O}^*(5^n)$. They also show a polynomial space algorithm running in time $\mathcal{O}^*(16^{n+o(n)})$. In this work, we show three main results: (i) A randomized polynomial space algorithm in time $\mathcal{O}^*(2^nD)$, where $D$ is the maximum distance between two cities. By using standard methods, this results in $(1+ε)$-approximation in time $\mathcal{O}^*(2^nε^{-1})$. Improving the constant $2$ in these results would be a major breakthrough, as it would result in improving the $\mathcal{O}^*(2^n)$-time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. (ii) A tight analysis of Berger et al.'s exponential space algorithm, resulting in $\mathcal{O}^*(4^n)$ running time bound. (iii) A new polynomial space algorithm, running in time $\mathcal{O}(7.88^n)$.
