Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/24207
Title: An analysis of the extended Christofides heuristic for the k-depot TSP
Authors: Xu, Z 
Xu, L
Rodrigues, B
Keywords: Approximation algorithms
Christofides heuristic
Multiple depots
TSP
Issue Date: 2011
Publisher: North-Holland
Source: Operations research letters, 2011, v. 39, no. 3, p. 218-223 How to cite?
Journal: Operations research letters 
Abstract: 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.
URI: http://hdl.handle.net/10397/24207
ISSN: 0167-6377
EISSN: 1872-7468
DOI: 10.1016/j.orl.2011.03.002
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

6
Last Week
0
Last month
0
Citations as of Oct 8, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Oct 15, 2017

Page view(s)

65
Last Week
7
Last month
Checked on Oct 22, 2017

Google ScholarTM

Check

Altmetric



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