TY - GEN

T1 - An O(log n) approximation ratio for the asymmetric traveling salesman path problem

AU - Chekuri, Chandra

AU - Pál, Martin

PY - 2006

Y1 - 2006

N2 - Given an arc-weighted directed graph G = (V,A,ℓ) and a pair of vertices s,t, we seek to 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 ATSPP. When s = t this is the well known asymmetric traveling salesman tour problem (ATSP). Although an O(logn) approximation ratio has long been known for ATSP, the best known ratio for ATSPPis O(√n). In this paper we present a polynomial time algorithm for ATSPPthat has approximation ratio of O(logn). 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.

AB - Given an arc-weighted directed graph G = (V,A,ℓ) and a pair of vertices s,t, we seek to 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 ATSPP. When s = t this is the well known asymmetric traveling salesman tour problem (ATSP). Although an O(logn) approximation ratio has long been known for ATSP, the best known ratio for ATSPPis O(√n). In this paper we present a polynomial time algorithm for ATSPPthat has approximation ratio of O(logn). 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.

UR - http://www.scopus.com/inward/record.url?scp=33750091916&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750091916&partnerID=8YFLogxK

U2 - 10.1007/11830924_11

DO - 10.1007/11830924_11

M3 - Conference contribution

AN - SCOPUS:33750091916

SN - 3540380442

SN - 9783540380443

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 95

EP - 103

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a

PB - Springer

T2 - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006

Y2 - 28 August 2006 through 30 August 2006

ER -