Name
Abstract | ||
|---|---|---|
We study an extension of the classical traveling salesman problem (TSP) to a situation with k=2 depots at each of which a distinct salesman is based. We show that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2-1/k, which improves on the known 2-approximation algorithm from the literature. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.orl.2011.03.002 | Oper. Res. Lett. |
Keywords | Field | DocType |
extended christofides heuristic,christofides heuristic,well-known christofides heuristic,tsp,non-trivial extension,approximation algorithms,salesman problem,2-approximation algorithm,k-depot tsp,tight approximation ratio,multiple depots,distinct salesman,traveling salesman problem | Approximation algorithm,Combinatorics,Vehicle routing problem,Mathematical optimization,Heuristic,Travelling salesman problem,Christofides algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 3 | Operations Research Letters |
Citations | PageRank | References |
5 | 0.52 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhou Xu | 1 | 47 | 5.15 |
| Liang Xu | 2 | 5 | 0.52 |
| Brian Rodrigues | 3 | 78 | 8.07 |