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
2051585135 1546311336 2038964811 2950432526
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 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. In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of [SIAM J. Comput. , 23 (1994), pp. 864--894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14--23]. We present approximation algorithms for 0-Extension . In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71--101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput. , 25 (1996), pp. 235--251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least @math for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations. 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.