*n*) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem

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

**Keywords:**combinatorial optimization, approximation algorithm, directed graph, traveling salesman problem, traveling salesman path, asymmetric triangle inequality

**Categories:**short, algorithms, approximation algorithms, combinatorial optimization, graphs, traveling salesman, commented on

**ACM Classification:**F.2.2, G.2.2

**AMS Classification:**68W25, 68R10, 90C59

**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.