An analysis of the extended Christofides heuristic for the k‐depot TSP

0.00 Avg rating—0 Votes

Article ID:	iaor20115244
Volume:	39
Issue:	3
Start Page Number:	218
End Page Number:	223
Publication Date:	May 2011
Journal:	Operations Research Letters
Authors:	Rodrigues Brian, Xu Zhou, Xu Liang
Keywords:	heuristics

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.

Reviews

Required fields are marked *. Your email address will not be published.