We consider some generalizations of the Asymmetric Traveling Salesman Path problem. Suppose we have an asymmetric metric G = (V,A) with two distinguished nodes s,t. We are also given a positive integer k. The goal is to find k paths of minimum total cost from s to t whose union spans all nodes. We call this the k-Person Asymmetric Traveling Salesmen Path problem (k-ATSPP). Our main result for k-ATSPP is a bicriteria approximation that, for some parameter b >= 1 we may choose, finds between k and k + k b paths of total length O(b log |V|) times the optimum value of an LP relaxation based on the Held-Karp relaxation for the Traveling Salesman problem. On one extreme this is an O(log |V|)-approximation that uses up to 2k paths and on the other it is an O(k log |V|)-approximation that uses exactly k paths. Next, we consider the case where we have k pairs of nodes (s_1,t_1), ..., (s_k,t_k). The goal is to find an s_i-t_i path for every pair such that each node of G lies on at least one of these paths. Simple approximation algorithms are presented for the special cases where the metric is symmetric or where s_i = t_i for each i. We also show that the problem can be approximated within a factor O(log n) when k=2. On the other hand, we demonstrate that the general problem cannot be approximated within any bounded ratio unless P = NP.
There is a linear programming (LP) relaxation for each of these problems based on the Held-Karp relaxation for TSP @cite_7 . For TSP, this relaxation is: [ ] Many of the approximation algorithms mentioned above also bound the integrality gap of the respective Held-Karp LP relaxation. For TSP, Wolsey @cite_0 proved the solutions found by Christofides' algorithm @cite_23 are within 3 2 of the optimal solution to the above LP relaxation. For ATSP, Williamson @cite_6 proved that the algorithm of Frieze @cite_8 bounds the integrality gap of its respective LP by @math . The improved @math -approximation for ATSP in @cite_15 improved the bound on gap to the same ratio. For TSP paths, An, Kleinberg and Shmoys @cite_14 first showed that Hoogeveen's algorithm bounds the integrality gap of a Held-Karp type relaxation for TSP paths by @math in cases where both endpoints are fixed. In the same paper they argue that their @math -approximation for this case also bounds the integrality gap by the same factor.
@cite_14 @cite_7 @cite_8 @cite_6 @cite_0 @cite_23 @cite_15
2051585135 2950391451 1546311336 2130517245
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 study integrality gaps and approximability of two closely related problems on directed graphs. Given a set V of n nodes in an underlying asymmetric metric and two specified nodes s and t, both problems ask to find an s-t path visiting all other nodes. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total cost of this path. In the directed latency problem, the objective is to minimize the sum of distances on this path from s to each node. Both of these problems are NP-hard. The best known approximation algorithms for ATSPP had ratio O(log n) until the very recent result that improves it to O(log n log log n). However, only a bound of O(sqrt(n)) for the integrality gap of its linear programming relaxation has been known. For directed latency, the best previously known approximation algorithm has a guarantee of O(n^(1 2+eps)), for any constant eps > 0. We present a new algorithm for the ATSPP problem that has an approximation ratio of O(log n), but whose analysis also bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. This solves an open problem posed by Chekuri and Pal [2007]. We then pursue a deeper study of this linear program and its variations, which leads to an algorithm for the k-person ATSPP (where k s-t paths of minimum total length are sought) and an O(log n)-approximation for the directed latency problem. 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 problem of obtaining the maximum a posteriori estimate of a general discrete Markov random field (i.e., a Markov random field defined using a discrete set of labels) is known to be NP-hard. However, due to its central importance in many applications, several approximation algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) LP-S: the linear programming (LP) relaxation proposed by Schlesinger (1976) for a special case and independently in (2001), (1998), and (2005) for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation of Ravikumar and Lafferty (2006); and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki (2003) for two label problems and later extended by (2006) for a general label set. We show that the SOCP-MS and the QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints objective function offered by QP and SOCP, the LP-S relaxation strictly dominates (i.e., provides a better approximation than) QP-RL and SOCP-MS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LP-S relaxation. Based on these results we propose some novel SOCP relaxations which define constraints using random variables that form cycles or cliques in the graphical model representation of the random field. Using some examples we show that the new SOCP relaxations strictly dominate the previous approaches.