Paper Info
Title
A 3/2-Approximation Algorithm For The Multiple Tsp With A Fixed Number Of Depots
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.
Year
DOI
Venue
2015
10.1287/ijoc.2015.0650
INFORMS JOURNAL ON COMPUTING
Keywords
Field
DocType
approximation algorithm, multiple depots, traveling salesman, matroid
Matroid,Approximation algorithm,Heuristic,Combinatorics,Mathematical optimization,Vehicle routing problem,Travelling salesman problem,Christofides algorithm,Mathematics
Journal
Volume
Issue
ISSN
27
4
1091-9856
Citations 
PageRank 
References 
2
0.41
11
Authors
2
Name
Order
Citations
PageRank
Zhou Xu120814.97
Brian Rodrigues2788.07