
Published: October 15, 2007
"On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem" by Viswanath Nagarajan, February 17, 2008
Abstract: [Plain Text Version]
We consider a variant of the traveling salesman problem (TSP): Given a directed graph G=(V,A) with non-negative arc lengths \lt\,:\, A \rightarrow \R^+ and a pair of vertices s,t, find an s-t walk of minimum length that visits all the vertices in V. If \lt 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.