pdf icon
Volume 3 (2007) Article 10 pp. 197-209
An   O(log n)   Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
Received: June 20, 2007
Published: October 15, 2007
Comments and updates on this paper:
"On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem" by Viswanath Nagarajan, February 17, 2008
Download article from ToC site:
[PDF (176K)] [PS (330K)] [Source ZIP]
Keywords: combinatorial optimization, approximation algorithm, directed graph, traveling salesman problem, traveling salesman path, asymmetric triangle inequality
ACM Classification: F.2.2, G.2.2
AMS Classification: 68W25, 68R10, 90C59

Abstract: [Plain Text Version]

$ \newcommand{\R}{{\mathbb R}} \newcommand{\atspp}{\text{ATSPP}} \newcommand{\atsp}{\text{ATSP}} \newcommand{\lt}{\ell} $

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.