ACM Transactions on Algorithms · 2007 · 71 citations · 13 references
ComputingComputer ScienceMathematicsAlgorithmsFault-tolerant ComputingFault-tolerant SystemsApproximation AlgorithmsCombinatorial OptimizationComputational ComplexityGraph AlgorithmsBest ApproximationPolynomial-time Approximation SchemeTraveling Salesman ApproximationTraveling Salesperson Problem ApproximationTree Algorithms
We consider the k -traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. We give a polynomial-time 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 of a metric. For the latter problem, a (2 + ε)-approximation is known. Our results can be compared with the best-known approximation algorithm using similar techniques for the case k = 1, which is 3.59α. Moreover, recent work of Chaudry et al. [2003] shows how to remove the factor of α, thus improving all of these results by that factor. 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 that can be more easily extended to the case of multiple repairmen, and may be of independent interest.
13
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
P-Complete Approximation Problems
Sartaj Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976 · 1.7K citations · Full text
Avrim Blum, Prasad Chalasani, Don Coppersmith et al. · 1994 · 316 citations
Paths, trees, and minimum latency tours
Kamalika Chaudhuri, Brighten Godfrey, Satish Rao et al. · 2004 · 176 citations