Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
2007; Springer Science+Business Media; Linguagem: Inglês
10.1007/978-3-540-74208-1_8
ISSN1611-3349
Autores Tópico(s)Complexity and Algorithms in Graphs
ResumoIn metric asymmetric traveling salesperson problems the input is a complete directed graph in which edge weights satisfy the triangle inequality, and one is required to find a minimum weight walk that visits all vertices. In the asymmetric traveling salesperson problem (ATSP) the walk is required to be cyclic. In asymmetric traveling salesperson path problem (ATSPP), the walk is required to start at vertex s and to end at vertex t. We improve the approximation ratio for ATSP from $\frac{4}{3}\log_3 n \simeq 0.84\log_2 n$ to $\frac{2}{3}\log_2 n$ . This improvement is based on a modification of the algorithm of Kaplan et al [JACM 05] that achieved the previous best approximation ratio. We also show a reduction from ATSPP to ATSP that loses a factor of at most 2 + ε in the approximation ratio, where ε> 0 can be chosen to be arbitrarily small, and the running time of the reduction is polynomial for every fixed ε. Combined with our improved approximation ratio for ATSP, this establishes an approximation ratio of $(\frac{4}{3} + \epsilon)\log_2 n$ for ATSPP, improving over the previous best ratio of 4log e n ≃ 2.76log2 n of Chekuri and Pal [Approx 2006].
Referência(s)