The Library
Fast minimum-weight double-tree shortcutting for metric TSP
Tools
Tools
Tools
Deineko, Vladimir G. and Tiskin, Alexander (2009) Fast minimum-weight double-tree shortcutting for metric TSP. Journal of Experimental Algorithmics, Vol.14 . 4.6. doi:10.1145/1498698.1594232 ISSN 1084-6654.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1145/1498698.1594232
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, that is, the minimum-weight double-tree shortcutting. Burkard et al. gave an algorithm for this problem, running in time O(n3 + 2d n2) and memory O(2d n2), where d is the maximum node degree in the rooted minimum spanning tree. We give an improved algorithm for the case of small d (including planar Euclidean TSP, where d ≤ 4), running in time O(4d n2) and memory O(4d n). This improvement allows one to solve the problem on much larger instances than previously attempted. Our computational experiments suggest that in terms of the time-quality trade-off, the minimum-weight double-tree shortcutting method provides one of the best existing tour-constructing heuristics.
| 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 | ||||
| Journal or Publication Title: | Journal of Experimental Algorithmics | ||||
| Publisher: | Association for Computing Machinery, Inc. | ||||
| ISSN: | 1084-6654 | ||||
| Official Date: | December 2009 | ||||
| Dates: |
|
||||
| Volume: | Vol.14 | ||||
| Page Range: | 4.6 | ||||
| DOI: | 10.1145/1498698.1594232 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
