Question

In Graph-Theory there are many ways for efficient approximation-algorithms to solve the Metric TSP. The best solution seems to be the Christofides Heuristic with a factor of 1.5 to the optimal solution. My Teacher said, there would be the so called $\frac{4}{3}$-conjecture, which states: there might be a approximation solution for the metric tsp, that has only a $\frac{4}{3}$-factor.

But i cannot find any literature or further information about this assumption. Maybe you can?

Was it helpful?

Solution

On the Integrality Gap of the Subtour LP for the 1,2-TSP provides some relevant references and discussion in the introduction..

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top