Computer Science – Data Structures and Algorithms
Scientific paper
2007-11-15
Computer Science
Data Structures and Algorithms
Scientific paper
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, i.e.\ the \emph{minimum-weight double-tree shortcutting}. Previously, we gave an efficient algorithm for this problem, and carried out its experimental analysis. In this paper, we address the related question of the worst-case approximation ratio for the minimum-weight double-tree shortcutting method. In particular, we give lower bounds on the approximation ratio in some specific metric spaces: the ratio of 2 in the discrete shortest path metric, 1.622 in the planar Euclidean metric, and 1.666 in the planar Minkowski metric. The first of these lower bounds is tight; we conjecture that the other two bounds are also tight, and in particular that the minimum-weight double-tree method provides a 1.622-approximation for planar Euclidean TSP.
Deineko Vladimir
Tiskin Alexander
No associations
LandOfFree
Minimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Minimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-215015