Volume 3 (2007)
Article 10 pp. 197-209
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
by Chandra Chekuri and Martin Pál
Received: June 20, 2007
Published: October 15, 2007
DOI: 10.4086/toc.2007.v003a010
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]
We consider a variant of the traveling salesman
problem (TSP). Given a directed graph
G=(
V,A) with non-negative arc lengths
ℓ : 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
ℓ
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(√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.
