TY - JOUR

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

AU - Deineko, Vladimir

AU - Tiskin, Alexander

PY - 2009/3/15

Y1 - 2009/3/15

N2 - 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 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. © 2009 Elsevier B.V. All rights reserved.

AB - 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 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. © 2009 Elsevier B.V. All rights reserved.

KW - approximation algorithms

KW - double-tree shortcutting

KW - Metric TSP

UR - http://www.scopus.com/inward/record.url?scp=61549137199&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2009.02.004

DO - 10.1016/j.endm.2009.02.004

M3 - Article

AN - SCOPUS:61549137199

VL - 32

SP - 19

EP - 26

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

IS - C

ER -