most recent 30 from http://www.or-exchange.com 2010-07-31T00:55:06Z http://www.or-exchange.com/feeds/question/132 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://www.or-exchange.com/questions/132/how-accurate-is-the-1-tree-lowerbound-for-the-tsp Daniel 2010-01-06T11:50:56Z 2010-06-02T19:04:21Z

<p>I'm having trouble finding an answer to this question:</p> <p>How accurately does a 1-tree reflect the weight of an optimal tour?</p> <p>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.</p> <p>I'm particularly interested in a theoretical justification.</p>

http://www.or-exchange.com/questions/132/how-accurate-is-the-1-tree-lowerbound-for-the-tsp/133#133 Michael Trick 2010-01-06T12:36:57Z 2010-01-06T12:36:57Z

<p>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.</p>

http://www.or-exchange.com/questions/132/how-accurate-is-the-1-tree-lowerbound-for-the-tsp/134#134 Matthew Saltzman 2010-01-06T13:24:37Z 2010-01-06T13:24:37Z

<p>The original paper is:</p> <p>M. Held and R.M. Karp, "The traveling-salesman problem and minimum spanning trees". Operations Research, 18, 1138-1162 (1970).</p> <p>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. </p> <p>There's a probabilistic analysis suggesting that the bound should be very good in practice. PDF is here:</p> <p><a href="http://dspace.mit.edu/bitstream/handle/1721.1/48871/probabilisticana00goem.pdf?sequence=1" rel="nofollow">http://dspace.mit.edu/bitstream/handle/1721.1/48871/probabilisticana00goem.pdf?sequence=1</a></p>

http://www.or-exchange.com/questions/132/how-accurate-is-the-1-tree-lowerbound-for-the-tsp/135#135 Alan Erera 2010-01-06T18:58:03Z 2010-01-06T18:58:03Z

<p>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, <em>Local Search in Combinatorial Optimization</em>, 1997.</p> <p>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 <em>Information Processing Letters</em>.</p> <p>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.</p>

http://www.or-exchange.com/questions/132/how-accurate-is-the-1-tree-lowerbound-for-the-tsp/410#410 Mohit Singh 2010-06-02T19:04:21Z 2010-06-02T19:04:21Z

<p>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. </p> <p>A simple 1-tree being the MST is also within 3/2 of the bound. </p>