سؤال

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?

هل كانت مفيدة؟

المحلول

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

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top