文章基本信息

标题：Many Visits TSP Revisited
本地全文：下载
作者：Åukasz Kowalik ; Shaohua Li ; Wojciech Nadara 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：66:1-66:22
DOI：10.4230/LIPIcs.ESA.2020.66
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 O*(5â¿). They also show a polynomial space algorithm running in time O(16^{n+o(n)}). In this work, we show three main results: - A randomized polynomial space algorithm in time O*(2^n D), where D is the maximum distance between two cities. By using standard methods, this results in a (1+Îµ)-approximation in time O*(2â¿Îµ^{-1}). Improving the constant 2 in these results would be a major breakthrough, as it would result in improving the O*(2â¿)-time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. - A tight analysis of Berger et al.âs exponential space algorithm, resulting in an O*(4â¿) running time bound. - A new polynomial space algorithm, running in time O(7.88â¿).
关键词：many visits traveling salesman problem; exponential algorithm