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.
 Abstract In their 1971 paper on the travelling salesman problem and minimum spanning trees, Held and Karp showed that finding an optimally weighted 1-tree is equivalent to solving a linear program for the traveling salesman problem (TSP) with only node-degree constraints and subtour elimination constraints. In this paper we show that the Held-Karp 1-trees have a certain monotonicity property: given a particular instance of the symmetric TSP with triangle inequality, the cost of the minimum weighted 1-tree is monotonic with respect to the set of nodes included. As a consequence, we obtain an alternate proof of a result of Wolsey and show that linear programs with node-degree and subtour elimination constraints must have a cost at least 2 3 OPT where OPT is the cost of the optimum solution to the TSP instance. We show that the traveling salesman problem with triangle inequality cannot be approximated with a ratio better than @math when the edge lengths are allowed to be asymmetric and @math when the edge lengths are symmetric, unless P=NP. The best previous lower bounds were @math and @math respectively. The reduction is from Hastad’s maximum satisfiability of linear equations modulo 2, and is nonconstructive. We consider two questions arising in the analysis of heuristic algorithms. (i) Is there a general procedure involved when analysing a particular problem heuristic? (ii) How can heuristic procedures be incorporated into optimising algorithms such as branch and bound?  Abstract : An O(n sup 3) heuristic algorithm is described for solving n-city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition. The algorithm involves as substeps the computation of a shortest spanning tree of the graph G defining the TSP, and the finding of a minimum cost perfect matching of a certain induced subgraph of G. A worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3 2. This represents a 50 reduction over the value 2 which was the previously best known such ratio for the performance of other polynomial-growth algorithms for the TSP. History (A. Hoffman and P. Wolfe). Motivation and Modeling (R. Garfinkel). Computational Complexity (D. Johnson and C. Papadimitriou). Well-Solved Special Cases (P. Gilmore, et al). Performance Guarantees for Heuristics (D. Johnson and C. Papadimitriou). Probabilistic Analysis of Heuristics (R. Karp and J. Steele). Empirical Analysis of Heuristics (B. Golden and W. Stewart). Polyhedral Theory (M. Grotschel and M. Padberg). Polyhedral Algorithms (M. Padberg and M. Grotschel). Branch and Bound Methods (E. Balas and P. Toth). Hamiltonian Cycles (V. Chvatal). Vehicle Routing (N. Christofides). Bibliography.