2003 · 63 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsFault-tolerant ComputingFault-tolerant SystemsApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsBest ApproximationMinimum Spanning Tree ProblemTree Algorithms
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.
6
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
Covering points in the plane by <i>k</i>-tours
Tetsuo Asano, Naoki Katoh, Hisao Tamaki et al. · 1997 · 66 citations
Algorithms for Capacitated Vehicle Routing
Moses Charikar, Samir Khuller, Balaji Raghavachari · SIAM Journal on Computing · 2001 · 50 citations