首页 | 本学科首页   官方微博 | 高级检索  
     


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/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:Traveling salesman problem   Subtour LP   Held&ndash  Karp bound   Integrality ratio Euclidean TSP
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号