Theory of Computing ------------------- Title : An   O(log n)   Approximation Ratio for the Asymmetric Traveling Salesman Path Problem Authors : Chandra Chekuri and Martin Pal Volume : 3 Number : 10 Pages : 197-209 URL : https://theoryofcomputing.org/articles/v003a010 Abstract -------- We consider a variant of the traveling salesman problem (TSP). Given a directed graph G=(V,A) with non-negative arc lengths \ell : A --> R+ and a pair of vertices s,t, find an s-t *walk* of minimum length that visits all the vertices in V. If \ell satisfies the *asymmetric* triangle inequality, the problem is equivalent to that of finding an s-t *path* of minimum length that visits all the vertices. We refer to this problem as the asymmetric traveling salesman path problem (ATSPP). When s = t this is the well known asymmetric traveling salesman tour problem (ATSP). Although an O(log n) approximation ratio has long been known for ATSP, the best known ratio for ATSPP is O(sqrt{n}). In this paper we present a polynomial time algorithm for ATSPP that has an approximation ratio of O(log n). The algorithm generalizes to the problem of finding a minimum length path or cycle that is required to visit a subset of vertices in a given order.