On the integrality ratio of the subtour LP for Euclidean TSP |
| |
Authors: | Stefan Hougardy |
| |
Affiliation: | Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, 53113 Bonn, Germany |
| |
Abstract: | ![]() A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is 4/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/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: | Traveling salesman problem Subtour LP Held&ndash Karp bound Integrality ratio Euclidean TSP |
本文献已被 ScienceDirect 等数据库收录! |