Fast minimum-weight double-tree shortcutting for metric TSP
Deineko, Vladimir and Tiskin, Alexander (2007) Fast minimum-weight double-tree shortcutting for metric TSP. In: 6th International Workshop on Experimental Algorithms, Rome, ITALY, JUN 06-08, 2007. Published in: Experimental Algorithms, Proceedings, 4525 pp. 136-149.Full text not available from this repository.
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:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||Experimental Algorithms, Proceedings|
|Number of Pages:||14|
|Page Range:||pp. 136-149|
|Title of Event:||6th International Workshop on Experimental Algorithms|
|Location of Event:||Rome, ITALY|
|Date(s) of Event:||JUN 06-08, 2007|
Actions (login required)