A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots

Publication Type

Journal Article

Publication Date

10-2015

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.

Keywords

approximation algorithm, multiple depots, traveling salesman, matroid

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

INFORMS Journal on Computing

Volume

27

Issue

4

First Page

636

Last Page

645

ISSN

1091-9856

Identifier

10.1287/ijoc.2015.0650

Publisher

INFORMS (Institute for Operations Research and Management Sciences)

Additional URL

https://doi.org/10.1287/ijoc.2015.0650

This document is currently not available here.

Share

COinS