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 finding 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.In addition, we give a simple proof of the 3.59αapproximation result which can be extended to the case of multiple repairmen.
展开▼
机译：我们考虑 k 个旅行修理工问题，这是度量旅行修理工问题（也称为最小等待时间问题）的推广，适用于多个修理工。为此，我们给出了8.497α逼近算法，其中α表示找到跨越 i 个顶点（ i - MST）问题。在 k = 1的情况下，这可以与最著名的近似算法进行比较，即3.59α。我们目前尚无关于此问题的可近似性的工作。此外，我们给出了3.59α近似结果的简单证明，可以将其扩展到多次修理的情况。
展开▼
