Minimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio

Simple item page
dc.creatorDeineko, Vladimir
dc.creatorTiskin, Alexander
dc.date2007-11-15
dc.date2008-12-28
dc.date.accessioned2026-07-07T12:22:18Z
dc.date.available2026-07-07T12:22:18Z
dc.descriptionThe 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.
dc.identifierhttps://arxiv.org/abs/0711.2399
dc.identifierhttp://arxiv.org/abs/0711.2399
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/213604
dc.subjectData Structures and Algorithms
dc.titleMinimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio
dc.typetext

Files

Collections

arXiv