Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143322 | Operations Research Letters | 2011 | 6 Pages |
Abstract
We study an extension of the classical traveling salesman problem (TSP) to a situation with kâ¥2 depots at each of which a distinct salesman is based. We show that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2â1/k, which improves on the known 2-approximation algorithm from the literature.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zhou Xu, Liang Xu, Brian Rodrigues,