The Travelling Salesman Problem is one the most fundamental and most studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with approximation factor of 3 2, even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only 4 3. Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis , and then by Momke and Svensson. In this paper, we provide an improved analysis for the approach introduced by Momke and Svensson yielding a bound of 13 9 on the approximation factor, as well as a bound of 19 12+epsilon for any epsilon>0 for a more general Travelling Salesman Path Problem in graphic metrics.
In the next section we present previous results relevant to the contributions of this paper, in particular we recall key definitions and theorems of M "omke and Svensson @cite_2 . In we present the improved upper bound on the cost of the core part of the circulation, as well as an almost matching lower bound. In we prove that the correction part of the circulation is essentially free. Finally, in we apply the results of the previous sections to obtain improved approximation algorithms for graphic TSP and TSPP.
@cite_2
2950432526
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4 3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.