作者
Zhou Xu, Liang Xu, Brian Rodrigues
发表日期
2011/5/1
期刊
operations research letters
卷号
39
期号
3
页码范围
218-223
出版商
North-Holland
简介
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.
学术搜索中的文章
Z Xu, L Xu, B Rodrigues - operations research letters, 2011