| | |
| | |
Stat |
Members: 3660 Articles: 2'599'751 Articles rated: 2609
10 November 2024 |
|
| | | |
|
Article overview
| |
|
Fast minimum-weight double-tree shortcutting for Metric TSP: Is the best one good enough? | Vladimir Deineko
; Alexander Tiskin
; | Date: |
1 Oct 2007 | 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 emph{minimum-weight double-tree shortcutting}. Burkard et al. gave an
algorithm for this problem, running in time $O(n^3+2^d n^2)$ and memory $O(2^d
n^2)$, 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 leq 4$), running in time $O(4^d n^2)$ and memory
$O(4^d 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 tradeoff, the minimum-weight double-tree
shortcutting method provides one of the best known tour-constructing
heuristics. | Source: | arXiv, 0710.0318 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|