A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots

Zhou Xu, Brian Rodrigues

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

We study a natural extension of the classical traveling salesman problem (TSP) in the situation where multiple salesmen are dispatched from a number of different depots. As with the TSP, this problem is motivated by a large range of applications in vehicle routing. Although it is known to have a 2-approximation algorithm, whether the problem has a 3/2-approximation algorithm, as is the case with the well-known Christofides heuristic for the TSP, remains an open question. We answer this question positively by providing a 3/2-approximation algorithm for the problem with a fixed number of depots. The algorithm uses an edge exchange strategy, and its analysis hinges on a newly discovered exchange property of matroids. In addition, the algorithm is applied to multidepot extensions of other TSP variants, and we show for the first time, to our knowledge, that for these multidepot extensions the same best constant approximation ratios can be achieved as for their respective single-depot cases.
Original languageEnglish
Pages (from-to)636-645
Number of pages10
JournalINFORMS Journal on Computing
Volume27
Issue number4
DOIs
Publication statusPublished - 1 Jan 2015

Keywords

  • Approximation algorithm
  • Matroid
  • Multiple depots
  • Traveling salesman

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Cite this