Standard

Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio. / Deineko, Vladimir; Tiskin, Alexander.

In: Electronic Notes in Discrete Mathematics, Vol. 32, No. C, 15.03.2009, p. 19-26.

Research output: Contribution to journal › Article › peer-review

Harvard

Deineko, V & Tiskin, A 2009, 'Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio', Electronic Notes in Discrete Mathematics, vol. 32, no. C, pp. 19-26. https://doi.org/10.1016/j.endm.2009.02.004

APA

Deineko, V., & Tiskin, A. (2009). Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio. Electronic Notes in Discrete Mathematics, 32(C), 19-26. https://doi.org/10.1016/j.endm.2009.02.004

Vancouver

Deineko V, Tiskin A. Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio. Electronic Notes in Discrete Mathematics. 2009 Mar 15;32(C):19-26. https://doi.org/10.1016/j.endm.2009.02.004

Author

Deineko, Vladimir ; Tiskin, Alexander. / Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio. In: Electronic Notes in Discrete Mathematics. 2009 ; Vol. 32, No. C. pp. 19-26.

BibTeX

@article{7205f945b6d6435a8726273136bb8325,
title = "Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio",
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, 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. {\textcopyright} 2009 Elsevier B.V. All rights reserved.",
keywords = "approximation algorithms, double-tree shortcutting, Metric TSP",
author = "Vladimir Deineko and Alexander Tiskin",
year = "2009",
month = mar,
day = "15",
doi = "10.1016/j.endm.2009.02.004",
language = "English",
volume = "32",
pages = "19--26",
journal = "Electronic Notes in Discrete Mathematics",
issn = "1571-0653",
publisher = "Elsevier",
number = "C",

}

RIS

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 -

ID: 127710302