Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142430 | Operations Research Letters | 2014 | 5 Pages |
Abstract
A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is 4/34/3. A well known family of graphic TSP instances achieves this lower bound asymptotically. For Euclidean TSP the best known lower bound on the integrality ratio was 8/78/7. We improve this value by presenting a family of Euclidean TSP instances for which the integrality ratio of the subtour LP converges to 4/3.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Stefan Hougardy,