Dove posso trovare letteratura sulla frac $ \ {4} {3} $ - congettura per approssimazione della metrica TSP?

Question

Nel grafico-teoria ci sono molti modi per efficienti di approssimazione-algoritmi per risolvere il Metric TSP. La soluzione migliore sembra essere il Christofides euristica con un fattore di 1,5 e la soluzione ottimale. Il mio Maestro ha detto, ci sarebbe il cosiddetto $ \ frac {4} {3} $ - congettura, che afferma: ci potrebbe essere una soluzione approssimazione per il cucchiaino di metrica, che ha solo un frac $ \ {4} {3} $ -factor.

Ma non riesco a trovare alcuna documentazione o ulteriori informazioni su questa ipotesi. Forse è possibile?

Answer 1

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