Paper Info
Title
Fast minimum-weight double-tree shortcutting for metric TSP: Is the best one good enough?
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(n3 + 2d n2) and memory O(2d n2), where d is the maximum node degree in the rooted minimum spanning tree. We give an improved algorithm for the case of small d (including planar Euclidean TSP, where d ≤ 4), running in time O(4d n2) and memory O(4d 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.
Year
DOI
Venue
2009
10.1145/1498698.1594232
ACM Journal of Experimental Algorithmics
Keywords
Field
DocType
planar euclidean tsp,tsp tour,classical np-hard optimization problem,metric tsp,improved algorithm,time o,memory o,minimum-weight double-tree,double-tree shortcutting method,minimum-weight double-tree shortcutting,good enough,minimum spanning tree,traveling salesman problem,optimization problem,computer experiment,approximation algorithms
Approximation algorithm,Discrete mathematics,Combinatorics,Mathematical optimization,Heuristics,Travelling salesman problem,Minimum weight,Euclidean geometry,Optimization problem,Mathematics,Whippletree,Minimum spanning tree
Journal
Volume
Citations 
PageRank 
14,
3
0.41
References 
Authors
11
2
Name
Order
Citations
PageRank
Vladimir G. Deineko136736.72
Alexander Tiskin222015.50