Access Restriction

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

   Open content in new tab
Source: ACM Digital Library