Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143150 | Operations Research Letters | 2007 | 7 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Waqar Malik, Sivakumar Rathinam, Swaroop Darbha,