After a sequence of improvements Boyd, Sitters, van der Ster, and Stougie proved that any 2-connected graph whose n vertices have degree 3, i.e., a cubic 2-connected graph, has a Hamiltonian tour of length at most (4 3)n, establishing in particular that the integrality gap of the subtour LP is at most 4 3 for cubic 2-connected graphs and matching the conjectured value of the famous 4 3 conjecture. In this paper we improve upon this result by designing an algorithm that finds a tour of length (4 3 - 1 61236)n, implying that cubic 2-connected graphs are among the few interesting classes of graphs for which the integrality gap of the subtour LP is strictly less than 4 3. With the previous result, and by considering an even smaller epsilon, we show that the integrality gap of the TSP relaxation is at most 4 3 - epsilon, even if the graph is not 2-connected (i.e. for cubic connected graphs), implying that the approximability threshold of the TSP in cubic graphs is strictly below 4 3. Finally, using similar techniques we show, as an additional result, that every Barnette graph admits a tour of length at most (4 3 - 1 18)n.
There have been several improvements for important special cases of the metric TSP in the last couple of years. Oveis Gharan, Saberi, and Singh @cite_1 design a @math -approximation algorithm for the case of graph metrics, while M "omke and Svensson @cite_16 improve that to @math , using a different approach. Mucha @cite_0 then showed that the approximation guarantee of the M "omke and Svensson algorithm is @math . Finally, still in the shortest path metric case, Seb "o and Vygen @cite_17 find an algorithm with a guarantee of @math . These results in particular show that the integrality gap of the subtour LP is below @math in case the metric comes from a graph. Another notable direction of recent improvements concern the @math path version of the TSP on arbitrary metrics, where the natural extension of Christofides' heuristic guarantees a solution within a factor of @math of optimum. An, Shmoys, and Kleinberg @cite_13 , find a @math -approximation algorithm this version of the TSP, while Seb "o @cite_4 further improved this result obtaining a @math -approximation algorithm.
@cite_4 @cite_1 @cite_0 @cite_16 @cite_13 @cite_17
1546311336 2950382808 2950432526 2051585135 1999799345
We prove the approximation ratio 8 5 for the metric s,t -path-TSP, and more generally for shortest connected T-joins. The algorithm that achieves this ratio is the simple "Best of Many" version of Christofides' algorithm (1976), suggested by An, Kleinberg and Shmoys (2012), which consists in determining the best Christofides s,t -tour out of those constructed from a family @math of trees having a convex combination dominated by an optimal solution x* of the Held-Karp relaxation. They give the approximation guarantee @math for such an s,t -tour, which is the first improvement after the 5 3 guarantee of Hoogeveen's Christofides type algorithm (1991). Cheriyan, Friggstad and Gao (2012) extended this result to a 13 8-approximation of shortest connected T-joins, for |T|≥4. The ratio 8 5 is proved by simplifying and improving the approach of An, Kleinberg and Shmoys that consists in completing x* 2 in order to dominate the cost of "parity correction" for spanning trees. We partition the edge-set of each spanning tree in @math into an s,t -path (or more generally, into a T-join) and its complement, which induces a decomposition of x*. This decomposition can be refined and then efficiently used to complete x* 2 without using linear programming or particular properties of T, but by adding to each cut deficient for x* 2 an individually tailored explicitly given vector, inherent in x*. A simple example shows that the Best of Many Christofides algorithm may not find a shorter s,t -tour than 3 2 times the incidentally common optima of the problem and of its fractional relaxation. 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. 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. We present a deterministic (1+√5 2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on @math vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides' algorithm is a 5 3-approximation algorithm for this problem, and this asymptotically tight bound in fact had been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides' algorithm variant. Our algorithm also proves an upper bound of 1+√5 2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP. We prove new results for approximating the graph-TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graph-TSP itself, we improve the approximation ratio to 7=5. For a generalization, the minimum T-tour problem, we obtain the first nontrivial approximation algorithm, with ratio 3=2. This contains the s-t-path graph-TSP as a special case. Our approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4=3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.