Theory of Computing
-------------------
Title     : An &nbsp; O(log <i>n</i>) &nbsp; Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
Authors   : Chandra Chekuri and Martin Pal
Volume    : 3
Number    : 10
Pages     : 197-209
URL       : http://www.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.