The Library
Min-weight double-tree shortcutting for metric TSP : bounding the approximation ratio
Tools
Tools
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. ISSN 1571-0653
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
sdarticle.pdf - Published Version Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 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 > Computer Science Faculty of Social Sciences > Warwick Business School |
| Journal or Publication Title: | Electronic Notes in Discrete Mathematics |
| Publisher: | Elsevier |
| ISSN: | 1571-0653 |
| Date: | 15 March 2009 |
| Volume: | Volume 32 |
| Page Range: | pp. 19-26 |
| Identification Number: | 10.1016/j.endm.2009.02.004 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), University of Warwick. Centre for Discrete Mathematics and Its Applications (DIMAP) |
| URI: | http://wrap.warwick.ac.uk/id/eprint/47510 |
Actions (login required)
 |
View Item |
