An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem Academic Article uri icon


  • In this paper, we present an algorithm with an approximation factor of 2 for a Generalized, Multiple Depot, Multiple Travelling Salesman Problem (GMTSP) when the costs are symmetric and satisfy the triangle inequality. The algorithm requires finding a degree constrained minimum spanning tree which we compute using a Lagrangian relaxation. 2007 Elsevier B.V. All rights reserved.

published proceedings


author list (cited authors)

  • Malik, W., Rathinam, S., & Darbha, S.

citation count

  • 44

complete list of authors

  • Malik, Waqar||Rathinam, Sivakumar||Darbha, Swaroop

publication date

  • November 2007