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

Zhou Xu, Liang Xu, Brian Rodrigues

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)


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-1k, which improves on the known 2-approximation algorithm from the literature.
Original languageEnglish
Pages (from-to)218-223
Number of pages6
JournalOperations Research Letters
Issue number3
Publication statusPublished - 1 May 2011


  • Approximation algorithms
  • Christofides heuristic
  • Multiple depots
  • TSP

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Cite this