The 4/3-Conjecture for Euclidean TSP

From himtp
Jump to: navigation, search

Problem Statement

The 4/3-Conjecture states that the integrality ratio of the subtour LP for metric TSP is at most 4/3. Prove this conjecture for Euclidean TSP.


Problem Background

The 4/3-Conjecture was posed in the mid-80th by several people. A well known graphic TSP example (pairwise connect the corners of two triangles by three long paths) shows that the value 4/3 is best possible. Wolsey [1] has shown that the integrality ratio of the subtour LP for metric TSP is at most 3/2. A proof of the 4/3-Conjecture would allow to approximate the length of an optimum TSP tour up to a factor of 4/3. This would improve the long-standing 3/2-approximation algorithm of Christofides [2] or metric TSP.

For graphic TSP the upper bound on the integrality ratio of the subtour LP was improved by Sebő and Vygen [3] to 7/5. Hougardy [4] recently proved that the integrality ratio of the subtour LP for Euclidean TSP is at least 4/3. Therefore, to prove the 4/3-Conjecture in its generality one also needs to be able to prove it for Euclidean TSP.


References

[1] Wolsey: Laurence A. Wolsey, Heuristic analysis, linear programming and branch and bound, Math. Program. Stud. 13 (1980) 121–134.

[2] Christofides: Worst-case Analysis of a New Heuristic for the Travelling Salesman Problem. Technical report, Carnegie-Mellon University, 1976.

[3] Sebő, Vygen: Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34 (5) (2014) 597-629.

[4] Hougardy: On the integrality ratio of the subtour LP for Euclidean TSP, Operations Research Letters 42 (2014), 495-499.


Comments