Many-visits TSP revisited

DOI10.1016/J.JCSS.2021.09.007MaRDI QIDQ2051856zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik, Shao-Hua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström

Publication date 25 November 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2005.02329

zbMATH Keywords

exponential algorithmmany-visits traveling salesman problem

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Abstract: 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}^{\ast }(5^n)$. They also show a polynomial space algorithm running in time $mathcal{O}^{\ast }(16^{n+o(n)})$. In this work, we show three main results: (i) A randomized polynomial space algorithm in time $mathcal{O}^{\ast }(2^{n}D)$, where $D$ is the maximum distance between two cities. By using standard methods, this results in $(1+epsilon)$-approximation in time $mathcal{O}^{\ast }(2^{n}epsilo{n}^{-1})$. Improving the constant $2$ in these results would be a major breakthrough, as it would result in improving the $mathcal{O}^{\ast }(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}^{\ast }(4^n)$ running time bound. (iii) A new polynomial space algorithm, running in time $mathcalO(7.88^n)$.

Recommendations

• A time- and space-optimal algorithm for the many-visits TSP
• Time- and space-optimal algorithm for the many-visits TSP
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• scientific article; zbMATH DE number 4053381
• Approximating asymmetric TSP in exponential time

Cites work

• A Dynamic Programming Approach for Sequencing Groups of Identical Jobs
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A framework for the complexity of high-multiplicity scheduling problems
• A probabilistic remark on algebraic program testing
• A time- and space-optimal algorithm for the many-visits TSP
• Algorithmic meta-theorems for restrictions of treewidth
• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Exact exponential algorithms.
• Expected Computation Time for Hamiltonian Path problem
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast witness extraction using a decision oracle
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• Lot sizing in a no-wait flow shop
• Low-complexity algorithms for sequencing jobs with a fixed number of job-classes
• Maximum Scatter TSP in Doubling Metrics
• On problems as hard as CNF-SAT
• On the complexity of k-SAT
• On the high multiplicity traveling salesman problem
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• Systems of distinct representatives and linear algebra
• The Traveling Salesman Problem with Many Visits to Few Cities
• Time- and space-optimal algorithm for the many-visits TSP
• Which problems have strongly exponential complexity?

Cited in

(8)

• On the high multiplicity traveling salesman problem
• On the parameterized complexity of the connected flow and many visits TSP problem
• scientific article; zbMATH DE number 4053381 (Why is no real title available?)
• Time- and space-optimal algorithm for the many-visits TSP
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• A time- and space-optimal algorithm for the many-visits TSP
• Preprocessing complexity for some graph problems parameterized by structural parameters
• Parameterized complexity of directed traveling salesman problem

This page was built for publication: Many-visits TSP revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051856)