| Article ID: | iaor2006321 |
| Country: | Netherlands |
| Volume: | 33 |
| Issue: | 5 |
| Start Page Number: | 467 |
| End Page Number: | 474 |
| Publication Date: | Sep 2005 |
| Journal: | Operations Research Letters |
| Authors: | Lewenstein Moshe, Sviridenko Maxim, Gamarnik David |
| Keywords: | programming: travelling salesman |
We consider the traveling salesman problem (TSP) on (the metric completion of) 3-edge-connected cubic graphs. These graphs are interesting because of the connection between their optimal solutions and the subtour elimination LP relaxation. Our main result is an approximation algorithm better than the 3/2-approximation algorithm for TSP in general.