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.
In metric asymmetric traveling salesperson problems the input is a complete directed graph in which edge weights satisfy the triangle inequality, and one is required to find a minimum weight walk that visits all vertices. In the asymmetric traveling salesperson problem (ATSP) the walk is required to be cyclic. In asymmetric traveling salesperson path problem (ATSPP), the walk is required to start at vertex sand to end at vertex t. We improve the approximation ratio for ATSP from @math to @math . This improvement is based on a modification of the algorithm of [JACM 05] that achieved the previous best approximation ratio. We also show a reduction from ATSPP to ATSP that loses a factor of at most 2 + i¾?in the approximation ratio, where i¾?> 0 can be chosen to be arbitrarily small, and the running time of the reduction is polynomial for every fixed i¾?. Combined with our improved approximation ratio for ATSP, this establishes an approximation ratio of @math for ATSPP, improving over the previous best ratio of 4log e ni¾? 2.76log 2 nof Chekuri and Pal [Approx 2006]. We consider the asymmetric traveling salesman problem for which the triangular inequality is satisfied. For various heuristics we construct examples to show that the worst-case ratio of length of tour found to minimum length tour is (n) for n city problems. We also provide a new O([log2n]) heuristic. 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.   This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k-TSPproblem: given an asymmetric metric (V,d), a root ri¾? Vand a target k≤ |V|, compute the minimum length tour that contains rand at least kother vertices. We present a polynomial time O(log2n·logk)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an O(log2n)-approximation algorithm for the directed orienteeringproblem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem from [2]. The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log2k) for directed k-TSP, and O(logn) for directed orienteering (Chekuri & Pal [4]). Using the algorithm for directed orienteering within the framework of [2] and [1], we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSPand the vehicle routing problem with time-windows. The traveling salesman problem comes in two variants. The symmetric version (STSP) assumes that the cost c sub ij of going to city i to city j is equal to c sub ji , while the more general asymmetric version (ATSP) does not make this assumption. In both cases, it is usually assumed that we are in the metric case, i.e., the costs satisfy the triangle inequality: c sub ij + c sub jk spl ges c sub ik for all i, j, k. In this assumption, we improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP (with triangle inequality) from 4 3 to 2. A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem, one can represent such a multigraph as a combination of at most n2 cycle covers, each taken with an appropriate multiplicity. We prove that if the d-regular multigraph does not contain more than ⌊d 2⌋ copies of any 2-cycle then we can find a similar decomposition into n2 pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such a decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give an alternative, simpler algorithm to extract a single such pair.This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum Traveling Salesman Problem (TSP) problem. The first stage of the rounding procedure obtains two cycle covers that do not share a 2-cycle with weight at least twice the weight of the optimal solution. Then we show how to extract a tour from the 2 cycle covers, whose weight is at least 2 3 of the weight of the longest tour. This improves upon the previous 5 8 approximation with a simpler algorithm. Utilizing a reduction from maximum TSP to the shortest superstring problem, we obtain a 2.5-approximation algorithm for the latter problem, which is again much simpler than the previous one.For minimum asymmetric TSP, the same technique gives two cycle covers, not sharing a 2-cycle, with weight at most twice the weight of the optimum. Assuming triangle inequality, we then show how to obtain from this pair of cycle covers a tour whose weight is at most 0.842 log 2 n larger than optimal. This improves upon a previous approximation algorithm with approximation guarantee of 0.999 log 2 n. Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2 3, previously 3 5) and maximum asymmetric TSP with triangle inequality (factor 10 13, previously 3 4). The Held-Karp heuristic for the Traveling Salesman Problem (TSP) has in practice provided near-optimal lower bounds on the cost of solutions to the TSP. We analyze the structure of Held-Karp solutions in order to shed light on their quality. In the symmetric case with triangle inequality, we show that a class of instances has planar solutions. We also show that Held-Karp solutions have a certain monotonicity property. This leads to an alternate proof of a result of Wolsey, which shows that the value of Held-Karp heuristic is always at least 2 3 OPT, where OPT is the cost of the optimum TSP tour. Additionally, we show that the value of the Held-Karp heuristic is equal to that of the linear relaxation of the biconnected-graph problem when edge costs are non-negative. In the asymmetric case with triangle inequality, we show that there are many equivalent definitions of the Held-Karp heuristic, which include finding optimally weighted 1-arborescences, 1-antiarborescences, asymmetric 1-trees, and assignment problems. We prove that monotonicity holds in the asymmetric case as well. These theorems imply that the value of the Held-Karp heuristic is no less than OPT and no less than the value of the Balas-Christofides heuristic for the asymmetric TSP. For the 1,2-TSP, we show that the Held-Karp heuristic cannot do any better than 9 10 OPT, even as the number of nodes tends to infinity. Portions of this thesis are joint work with David Shmoys.