### Fast minimum-weight double-tree shortcutting for metric TSP: Is the best one good enough?Fast minimum-weight double-tree shortcutting for metric TSP: Is the best one good enough?

Access Restriction
Subscribed

 Author Deineko, Vladimir ♦ Tiskin, Alexander Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Approximation algorithms ♦ Metric TSP ♦ Double-tree shortcutting Abstract The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponentially-sized space of TSP tours, each of which approximates the optimal solution within, at most, a factor of 2. We consider the problem of finding among these tours the one that gives the closest approximation, that is, the minimum-weight double-tree shortcutting. Burkard et al. gave an algorithm for this problem, running in time $O(n^{3}$ + $2^{d}$ $n^{2})$ and memory $O(2^{d}$ $n^{2}),$ where $\textit{d}$ is the maximum node degree in the rooted minimum spanning tree. We give an improved algorithm for the case of small $\textit{d}$ (including planar Euclidean TSP, where $\textit{d}$ ≤ 4), running in time $O(4^{d}$ $n^{2})$ and memory $O(4^{d}$ $\textit{n}).$ This improvement allows one to solve the problem on much larger instances than previously attempted. Our computational experiments suggest that in terms of the time-quality trade-off, the minimum-weight double-tree shortcutting method provides one of the best existing tour-constructing heuristics. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-01-05 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 14 Page Count 11 Starting Page 4.6 Ending Page 4.16

#### Open content in new tab

Source: ACM Digital Library