Paper Info
Title
(P-1)/(P+1)-Approximate Algorithms For P-Traveling Salesmen Problems On A Tree With Minmax Objective
Abstract
Suppose p traveling salesmen must visit together all points/nodes of a tree, and the objective is to minimize the maximum of lengths of their tours. For location-allocation problems (where both optimal home locations of the salesmen and their tours must be found), which are NP-complete, fast polynomial heuristics with worst-case relative error (p - 1)/(p + 1) are presented.
Year
DOI
Venue
1997
10.1016/S0166-218X(97)89161-5
DISCRETE APPLIED MATHEMATICS
Keywords
DocType
Volume
traveling salesman, approximate algorithms, complexity
Journal
75
Issue
ISSN
Citations 
3
0166-218X
5
PageRank 
References 
Authors
0.80
0
2
Name
Order
Citations
PageRank
Igor Averbakh169954.76
O. Berman21604231.36