The k-traveling repairman problem
Jittat Fakcharoenphol, Chris Harrelson, Satish B. Rao · 2003
We consider the k-traveling repairman problem, a generalization of the metric traveling repairman problem, also known as the minimum latency problem, to multiple repairmen. We give an 8:497-approximation algorithm for this generalization, where denotes the best achievable approximation factor for the problem of nding the least cost rooted tree spanning i vertices (i-MST) problem. This can be compared with the best known approximation algorithm for the case k = 1, which is 3:59. We are aware of no previous work on the approximability of the present problem.