Article ID Journal Published Year Pages File Type
10524007 Operations Research Letters 2005 8 Pages PDF
Abstract
We consider the travelling salesman problem (TSP) problem 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.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
An improved upper bound for the TSP in cubic 3-edge-connected graphs
Authors
, , ,