The Asymmetric Traveling Salesperson Path Problem (ATSPP) is one where, given an asymmetric metric space @math with specified vertices s and t, the goal is to find an s-t path of minimum length that passes through all the vertices in V. This problem is closely related to the Asymmetric TSP (ATSP), which seeks to find a tour (instead of an @math path) visiting all the nodes: for ATSP, a @math -approximation guarantee implies an @math -approximation for ATSPP. However, no such connection is known for the integrality gaps of the linear programming relaxations for these problems: the current-best approximation algorithm for ATSPP is @math , whereas the best bound on the integrality gap of the natural LP relaxation (the subtour elimination LP) for ATSPP is @math . In this paper, we close this gap, and improve the current best bound on the integrality gap from @math to @math . The resulting algorithm uses the structure of narrow @math - @math cuts in the LP solution to construct a (random) tree spanning tree that can be cheaply augmented to contain an Eulerian @math - @math walk. We also build on a result of Oveis Gharan and Saberi and show a strong form of Goddyn's conjecture about thin spanning trees implies the integrality gap of the subtour elimination LP relaxation for ATSPP is bounded by a constant. Finally, we give a simpler family of instances showing the integrality gap of this LP is at least 2.
The first non-trivial approximation for ATSPP was an @math -approximation by Lam and Newman @cite_2 . This was improved to @math by Chekuri and P 'al @cite_6 , and the constant was further improved in @cite_1 . The paper @cite_1 also showed that ATSP and ATSPP had approximability within a constant factor of each other. All these results are combinatorial and do not bound integrality gap of ATSPP. A bound of @math on the integrality gap of ATSPP was given by Nagarajan and Ravi @cite_10 , and was improved to @math by Friggstad, Salavatipour and Svitkina @cite_3 . Note that there is still no result known that relates the integrality gaps of the ATSP and ATSPP problems in a black-box fashion.
@cite_1 @cite_3 @cite_6 @cite_2 @cite_10
2137717103 2950391451 330417094 1976231547 1492330513
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 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. Compounds corresponding to the formula: I wherein Z represents a radical which completes a condensed aromatic ring system; R1 represents an n-valent aliphatic or aromatic radical; R2 represents H, alkyl or aryl, R3 represents one or more radicals to control the diffusion properties and the activation pH; and n represents 1 or 2, are suitable ED precursor compounds for use in color-photographic recording materials. They are preferably used in a combination with reducible dye-releasers. They are also suitable as so-called scavengers. In the traveling salesman path problem, we are given a set of cities, traveling costs between city pairs and fixed source and destination cities. The objective is to find a minimum cost path from the source to destination visiting all cities exactly once. In this paper, we study polyhedral and combinatorial properties of a variant we call the traveling salesman walk problem, in which the objective is to find a minimum cost walk from the source to destination visiting all cities at least once. We first characterize traveling salesman walk perfect graphs, graphs for which the convex hull of incidence vectors of traveling salesman walks can be described by linear inequalities. We show these graphs have a description by way of forbidden minors and also characterize them constructively. We also address the asymmetric traveling salesman path problem (ATSPP) and give a factor @math -approximation algorithm for this problem. We study the directed minimum latency problem: given an n-vertex asymmetric metric (V,d) with a root vertex ri¾? V, find a spanning path originating at rthat minimizes the sum of latencies at all vertices (the latency of any vertex vi¾? Vis the distance from rto valong the path). This problem has been well-studied on symmetric metrics, and the best known approximation guarantee is 3.59 [3]. For any @math O( n^ ^3 ) @math =O( n )$, which implies (for any fixed i¾?> 0) a polynomial time O(n1 2 + i¾?)-approximation algorithm for directed latency. In the special case of metrics induced by shortest-paths in an unweighted directed graph, we give an O(log2n) approximation algorithm. As a consequence, we also obtain an O(log2n) approximation algorithm for minimizing the weighted completion time in no-wait permutation flowshop scheduling. We note that even in unweighted directed graphs, the directed latency problem is at least as hard to approximate as the well-studied asymmetric traveling salesman problem, for which the best known approximation guarantee is O(logn).