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

Chandra Chekuri, Martin Pál

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a
PublisherSpringer
Pages95-103
Number of pages9
ISBN (Print)3540380442, 9783540380443
DOIs
StatePublished - 2006
Externally publishedYes
Event9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 - Barcelona, Spain
Duration: Aug 28 2006Aug 30 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4110 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006
Country/TerritorySpain
CityBarcelona
Period8/28/068/30/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'An O(log n) approximation ratio for the asymmetric traveling salesman path problem'. Together they form a unique fingerprint.

Cite this