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-1k, which improves on the known 2-approximation algorithm from the literature.
- Approximation algorithms
- Christofides heuristic
- Multiple depots
ASJC Scopus subject areas
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics