An Analysis of the Extended Christofides Heuristic for the k-depot Travelling Salesman Problem

Author

Zhou XU
Liang XU
Brian Charles RODRIGUES, Singapore Management UniversityFollow

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