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
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
"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, comment added
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.
Licensed under a Creative Commons License