Deineko, Vladimir G. and Tiskin, Alexander. (2009) Min-Weight Double-Tree Shortcutting for Metric TSP: Bounding the Approximation Ratio. Electronic Notes in Discrete Mathematics, 32 . pp. 19-26. ISSN 1571-0653

Full text not available from this repository.

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:	32
Page Range:	pp. 19-26
Identification Number:	10.1016/j.endm.2009.02.004
Publication Status:	Published
Related URLs:	Other Repository
URI:	http://wrap.warwick.ac.uk/id/eprint/47510

Request changes to a record

Actions (login required)

View Item