The Library
Min-weight double-tree shortcutting for metric TSP : bounding the approximation ratio
Tools
Deineko, Vladimir G. and Tiskin, Alexander (2009) Min-weight double-tree shortcutting for metric TSP : bounding the approximation ratio. Electronic Notes in Discrete Mathematics, Volume 32 . pp. 19-26. doi:10.1016/j.endm.2009.02.004 ISSN 1571-0653.
PDF
sdarticle.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (437Kb) |
Official URL: http://dx.doi.org/10.1016/j.endm.2009.02.004
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Social Sciences > Warwick Business School |
||||
Journal or Publication Title: | Electronic Notes in Discrete Mathematics | ||||
Publisher: | Elsevier | ||||
ISSN: | 1571-0653 | ||||
Official Date: | 15 March 2009 | ||||
Dates: |
|
||||
Volume: | Volume 32 | ||||
Page Range: | pp. 19-26 | ||||
DOI: | 10.1016/j.endm.2009.02.004 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 21 December 2015 | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC), University of Warwick. Centre for Discrete Mathematics and Its Applications (DIMAP) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |