An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem Academic Article uri icon

abstract

  • 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.

author list (cited authors)

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

citation count

  • 37

publication date

  • November 2007