An Improved Upper Bound for the TSP in 3-Connected Cubic Graphs

We consider the classical minimum Travelling Salesman Problem on the class of 3-edge-connected cubic graphs. More specifically we consider their (shortest path) metric completions. The well-known conjecture states that the subtour elimination LP relaxation on the min TSP yields a 4/3 approximation factor, yet the best known ap-proximation factor is 3/2. The 3-edge-connected cubic graphs have the special property of being ”LP-oblivious” to the subtour elimination LP relaxation and hence provide a class that potentially would show a tight 3/2 bound. However, we show that on this class of graphs one can achieve an approximation factor better than the general 3/2.

By: Maxim I. Sviridenko, D. Gamarnik, M. Lewenstein

Published in: Operations Research Letters, volume 33, (no 5), pages 467-74 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .