Deineko, Vladimir G. and Tiskin, Alexander (2007) Fast minimum-weight double-tree shortcutting for metric TSP. In: Demetrescu, C., (ed.) Experimental Algorithms. Lecture Notes in Computer Science, Volume 4525 . Springer Berlin Heidelberg, pp. 136-149. ISBN 9783540728443

PDF fulltext9.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (481Kb)

Request Changes to record.

Abstract

The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponential-sized space of TSP tours, each of which is a 2-approximation to the exact solution. We consider the problem of minimum-weight double-tree shortcutting, for which Burkard et al. gave an algorithm running in time O(2(d)n(3)) and memory O(2(d)n(2)), where d is the maximum node degree in the rooted minimum spanning tree (e.g. in the non-degenerate planar Euclidean case, d <= 4). We give an improved algorithm running in time O(4(d)n(2)) and memory O(4(d)n), which allows one to solve the problem on much larger instances. Our computational experiments suggest that the minimum-weight double-tree shortcutting method provides one of the best known tour-constructing heuristics.

Item Type:	Book Item
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Series Name:	Lecture Notes in Computer Science
Journal or Publication Title:	Experimental Algorithms, Proceedings
Publisher:	Springer Berlin Heidelberg
ISBN:	9783540728443
ISSN:	0302-9743
Book Title:	Experimental Algorithms
Editor:	Demetrescu, C.
Official Date:	2007
Dates:	Date Event 2007 Published
Volume:	Volume 4525
Number of Pages:	14
Page Range:	pp. 136-149
Status:	Peer Reviewed
Publication Status:	Published
Date of first compliant deposit:	14 December 2015
Conference Paper Type:	Paper
Title of Event:	6th International Workshop on Experimental Algorithms
Type of Event:	Workshop
Location of Event:	Rome, Italy
Date(s) of Event:	06-08 Jun 2007

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item