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.