32–approximation algorithm for two variants of a 2-depot Hamiltonian path problem Academic Article uri icon

abstract

  • We consider two variants of a 2-depot Hamiltonian path problem and show that they have an algorithm with an approximation ratio of frac(3, 2) if the costs are symmetric and satisfy the triangle inequality. This improves the 2-approximation algorithm already available for the problem. © 2009 Elsevier B.V. All rights reserved.

author list (cited authors)

  • Rathinam, S., & Sengupta, R.

citation count

  • 14

publication date

  • January 2010