| 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, 
											