Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
TSP on Cubic and Subcubic Graphs
verfasst von : Sylvia Boyd, René Sitters, Suzanne van der Ster, Leen Stougie
Erschienen in: Integer Programming and Combinatoral Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the Travelling Salesman Problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3 conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal values of the TSP and its linear programming relaxation, is 4/3. Using polyhedral techniques in an interesting way, we obtain a polynomial-time 4/3-approximation algorithm for this problem on cubic graphs, improving upon Christofides’ 3/2-approximation, and upon the 3/2 − 5/389 ≈ 1.487-approximation ratio by Gamarnik, Lewenstein and Svirdenko for the case the graphs are also 3-edge connected. We also prove that, as an upper bound, the 4/3 conjecture is true for this problem on cubic graphs. For subcubic graphs we obtain a polynomial-time 7/5-approximation algorithm and a 7/5 bound on the integrality gap.