Approximation algorithms for multiple terminal, Hamiltonian path problems Academic Article uri icon


  • This article presents a new 2-approximation algorithm for a multiple depot, multiple terminal, Hamiltonian path problem when the costs satisfy the triangle inequality. For the case where all the salesmen start from the same depot, we present another algorithm with an approximation ratio of 5/3. These results generalize the approximation algorithms currently available for the single depot, single terminal Hamiltonian path problem. © 2010 Springer-Verlag.

author list (cited authors)

  • Bae, J., & Rathinam, S.

citation count

  • 8

publication date

  • October 2010