Name
Title | ||
|---|---|---|
An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem |
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.orl.2007.02.001 | Oper. Res. Lett. |
Keywords | Field | DocType |
triangle inequality,approximation factor,approximation algorithm,multiple travelling salesman,multiple depot,lagrangian relaxation,symmetric generalized multiple depot,satisfiability,travelling salesman problem,travelling salesman,vehicle routing,approximation algorithms,minimum spanning tree | Nearest neighbour algorithm,Approximation algorithm,Vehicle routing problem,Mathematical optimization,Combinatorics,Travelling salesman problem,Christofides algorithm,Spanning tree,Lagrangian relaxation,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
35 | 6 | Operations Research Letters |
Citations | PageRank | References |
22 | 1.59 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Waqar Malik | 1 | 39 | 3.86 |
| Sivakumar Rathinam | 2 | 216 | 23.81 |
| Swaroop Darbha | 3 | 184 | 26.64 |