An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem
Publication Type
Journal Article
Publication Date
5-2011
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.
Keywords
Approximation algorithms, Christofides heuristic, Multiple depots, TSP
Discipline
Operations and Supply Chain Management
Research Areas
Operations Management
Publication
Operations Research Letters
Volume
39
Issue
3
First Page
218
Last Page
223
ISSN
0167-6377
Identifier
10.1016/j.orl.2011.03.002
Publisher
Elsevier
Citation
XU, Zhou; XU, Liang; and RODRIGUES, Brian Charles.
An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem. (2011). Operations Research Letters. 39, (3), 218-223.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/4920
Additional URL
https://doi.org/10.1016/j.orl.2011.03.002
