Name
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(2dn3) and memory O(2dn2), 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(4dn2) and memory O(4dn), 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-72845-0_11 | WEA |
Keywords | Field | DocType |
optimization problem,computer experiment,exact solution,minimum spanning tree,traveling salesman problem | Exact solutions in general relativity,Combinatorics,Hamiltonian path,Travelling salesman problem,Heuristics,Minimum weight,Euclidean geometry,Optimization problem,Mathematics,Minimum spanning tree | Conference |
Volume | ISSN | Citations |
4525 | 0302-9743 | 4 |
PageRank | References | Authors |
0.45 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vladimir G. Deineko | 1 | 367 | 36.72 |
| Alexander Tiskin | 2 | 220 | 15.50 |