Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/68287
Title: A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
Authors: Xu, Z 
Rodrigues, B
Keywords: Approximation algorithm
Multiple depots
Traveling salesman
Matroid
Issue Date: 2015
Publisher: INFORMS
Source: Informs journal on computing, 2015, v. 27, no. 4, p. 636-645 How to cite?
Journal: Informs journal on computing 
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.
URI: http://hdl.handle.net/10397/68287
ISSN: 1091-9856
EISSN: 1526-5528
DOI: 10.1287/ijoc.2015.0650
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

2
Last Week
0
Last month
Citations as of Nov 17, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
Citations as of Nov 18, 2017

Page view(s)

47
Last Week
7
Last month
Checked on Nov 19, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.