The k-traveling repairmen problem

ABSTRACT

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.

REFERENCES

• 1: Archer, A., Levin, A., and Williamson, D. P. 2003. A faster, better approximation algorithm for the minimum latency problem. Tech. Rep. 1362, Cornell University.
• 2: Aaron Archer , David P. Williamson, Faster approximation algorithms for the minimum latency problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 3: Sanjeev Arora , George Karakostas, Approximation schemes for minimum latency problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.688-693, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301432]
• 4: Sanjeev Arora , George Karakostas, A 2 + &egr; approximation algorithm for the k-MST problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.754-759, January 09-11, 2000, San Francisco, California, United States
• 5: Tetsuo Asano , Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.275-283, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258602]
• 6: Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
• 7: Moses Charikar , Samir Khuller , Balaji Raghavachari, Algorithms for Capacitated Vehicle Routing, SIAM Journal on Computing, v.31 n.3, p.665-682, 2001 [doi>10.1137/S0097539701392056]
• 8: Kamalika Chaudhuri , Brighten Godfrey , Satish Rao , Kunal Talwar, Paths, Trees, and Minimum Latency Tours, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.36, October 11-14, 2003
• 9: Chandra Chekuri , Anupam Gupta , Amit Kumar , Joseph (Seffi) Naor , Danny Raz, Building Edge-Failure Resilient Networks, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.439-456, May 27-29, 2002
• 10: Chekuri, C., and Kumar, A. 2004. Maximum coverage problem with group budget constraints and applications. http://cm.bell-labs.com/cm/cs/who/chekuri/postscript/coverage.ps.
• 11: Christofides, N. 1985. The Traveling Salesman Problem. John Wiley, New York, 431--448.
• 12: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 13: N. Garg, A 3-approximation for the minimum tree spanning k vertices, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.302, October 14-16, 1996
• 14: Michel Goemans , Jon Kleinberg, An improved approximation ratio for the minimum latency problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.152-158, January 28-30, 1996, Atlanta, Georgia, United States
• 15: Haimovich, M., Kan, A. R., and Stougie, L. 1988. Analysis for heuristics for vehicle routing problems. In Vehicle Routing: Methods and Studies. Elsevier Science, Chapter 3.
• 16: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 17: René Sitters, The Minimum Latency Problem Is NP-Hard for Weighted Trees, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.230-239, May 27-29, 2002
• 18: Toth, P., and Vigo, D., eds. 2002. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
Traveling salesman, vehicle routing