
arXiv: 1907.10376
We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an $��$-approximation algorithm for TSP, then, for any $��>0$, there is an $(��+��)$-approximation algorithm for the more general Path TSP. This reduction implies that the approximability of Path TSP is the same as for TSP, up to an arbitrarily small error. This avoids future discrepancies between the best known approximation factors achievable for these two problems, as they have existed until very recently. A well-studied special case of TSP, Graph TSP, asks for tours in unit-weight graphs. Our reduction shows that any $��$-approximation algorithm for Graph TSP implies an $(��+��)$-approximation algorithm for its path version. By applying our reduction to the $1.4$-approximation algorithm for Graph TSP by Seb�� and Vygen, we obtain a polynomial-time $(1.4+��)$-approximation algorithm for Graph Path TSP, improving on a recent $1.497$-approximation algorithm of Traub and Vygen. We obtain our results through a variety of new techniques, including a novel way to set up a recursive dynamic program to guess significant parts of an optimal solution. At the core of our dynamic program we deal with instances of a new generalization of (Path) TSP which combines parity constraints with certain connectivity requirements. This problem, which we call $��$-TSP, has a constant-factor approximation algorithm and can be reduced to TSP in certain cases when the dynamic program would not make sufficient progress.
FOS: Computer and information sciences, Combinatorial optimization, Discrete Mathematics (cs.DM), traveling salesman problem, Dynamic programming, Approximation algorithms, path TSP, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), approximation algorithm, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Combinatorial optimization, Discrete Mathematics (cs.DM), traveling salesman problem, Dynamic programming, Approximation algorithms, path TSP, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), approximation algorithm, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 19 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
