  
  
Stat 
Members: 3660 Articles: 2'599'751 Articles rated: 2609
10 November 2024 

   

Article overview
 

Fast minimumweight doubletree 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 NPhard
optimization problem. The doubletree shortcutting method for Metric TSP yields
an exponentiallysized 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{minimumweight doubletree 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 timequality tradeoff, the minimumweight doubletree
shortcutting method provides one of the best known tourconstructing
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.

 


