|
1
|
I'm having trouble finding an answer to this question: How accurately does a 1-tree reflect the weight of an optimal tour? I know there are lots papers studying the various ways optimise a 1-tree (by trying to find a 1-tree where every node has degree 2) but I'm interested in a simple non-optimised 1-tree. I'm particularly interested in a theoretical justification. |
||
|
|
|
1
|
Assuming the triangle inequality, the minimum spanning tree is within a factor of 2 of optimal, so the minimum one-tree is also within a factor of 2. Seems clear that there are examples where this is tight. |
||||||
|
|
3
|
A good reference providing a thorough introduction to the TSP with a focus on heuristics is Johnson and McGeoch "The Traveling Salesman Problem: A Case Study in Local Optimization", a chapter in Aarts and Lenstra, Local Search in Combinatorial Optimization, 1997. The chapter reports that the Held-Karp bound for any TSP instance I satisfying the triangle inequality, L^{HK}(I), cannot not be smaller than (2/3) L^{OPT}(I), where L^{OPT}(I) is the optimal tour length. This result is attributed to both Wolsey (1980) and Shmoys and Williamson (1990); the latter paper is "Analyzing the Held-Karp TSP Bound: A monotonicity property and applications" in Information Processing Letters. As far as empirical performance, the Johnson and McGeoch chapter provides a nice analysis of an implementation of the Lin-Kernighan TSP heuristic. For Lin-Kernighan tours found for random Euclidean instances with sizes ranging from n=100 to 1,000,000, the average percentage length in excess of the H-K bound is never greater than 2%; this very small average indicates that the H-K bound is quite tight for such instances in practice. Unfortunately, they do not report maximum excesses. |
||
|
|
|
2
|
The original paper is: M. Held and R.M. Karp, "The traveling-salesman problem and minimum spanning trees". Operations Research, 18, 1138-1162 (1970). The result is that the bound is equivalent to an LP-relaxation bound from a standard IP formulation. I haven't read the original paper, so I can't elaborate on the details, but AIUI, basically, this is a Lagrangian relaxation with the integrality property. There's a probabilistic analysis suggesting that the bound should be very good in practice. PDF is here: http://dspace.mit.edu/bitstream/handle/1721.1/48871/probabilisticana00goem.pdf?sequence=1 |
||
|
|
|
1
|
As pointed above, best 1-tree bound equals the bound from the subtour elimination LP. It is known that the best tour is within 3/2 of this bound (Christofides Algorithm) and there are examples where best tour is at least 4/3 times this bound. A simple 1-tree being the MST is also within 3/2 of the bound. |
||
|
|
