Asymmetric traveling salesman path and directed latency problems (Conference Paper)

摘要

We study integrality gaps and approximability of three closely related problems on directed graphs with edge lengths that satisfy the triangle inequality. Given two specified vertices s and t, two of these problems ask to find an s-t path in the graph visiting all other vertices. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total length of this path. In the directed latency problem, the objective is to minimize the sum of the latencies of the vertices, where the latency of a vertex v is the distance from s to v along the path. The third problem that we study is the k-person ATSPP, in which the goal is to find k paths from s to t, of minimum total length, such that every vertex is on at least one of these paths. All of these problems are NP-hard. The best known approximation algorithms for ATSPP had ratio O(logn) [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197-209], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107-118] until the recent result that improves it to O(logn/loglogn) [A. Asadpour et al., "An O(logn/log log n)-approximation algorithm for the asymmetric traveling salesman problem," in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 379-389], [U. Feige and M. Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs," in Proceedings of the 10th APPROX, 2007, pp. 107-118]. However, the best known bound on the integrality gap of any linear programming relaxation for ATSPP is only O(√n). For directed latency, the best previously known approximation algorithm has a guarantee of O(n1/2+ε) for any constant ε > 0 [V. Nagarajan and R. Ravi, "The directed minimum latency problem," in Proceedings of the 11th APPROX, 2008, pp. 193-206]. We present a new algorithm for the ATSPP problem that has an approximation ratio of O(logn), but whose analysis also upper bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. This solves an open problem posed in [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197-209]. We then pursue a deeper study of this linear program and its variations, which leads to an O(logn)-approximation for the directed latency problem, a significant improvement over previously known results. Our result for k-person ATSPP is an O(k logn)-approximation that bounds the integrality gap of a linear programming relaxation by the same factor. We are not aware of any previous work on this problem.