An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem
- Additional Document Info
- View All
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.