Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/29504
Title: Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree
Authors: Xu, L
Xu, Z 
Xu, D
Keywords: Exact algorithm
Approximation algorithm
Min- max
K-Traveling salesmen problem
Tree
Issue Date: 2013
Publisher: Elsevier
Source: European journal of operational research, 2013, v. 227, no. 2, p. 284-292 How to cite?
Journal: European journal of operational research 
Abstract: Given k identical salesmen, where k ≥ 2 is a constant independent of the input size, the min–max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ≥ 2, closing a question that has remained open for a decade. Along with this, we have further developed a (1 + ϵ)-approximation algorithm for any ϵ > 0.
URI: http://hdl.handle.net/10397/29504
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2012.12.023
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

8
Last Week
0
Last month
Citations as of Jun 14, 2018

WEB OF SCIENCETM
Citations

4
Last Week
0
Last month
0
Citations as of Jun 18, 2018

Page view(s)

70
Last Week
0
Last month
Citations as of Jun 17, 2018

Google ScholarTM

Check

Altmetric


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