LAUSR

We consider a multiple-depots extension of the classic Hamiltonian path problem where k salesmen are initially located at different depots. To the best of our knowledge, no algorithm for this problem with a constant approximation ratio has been previously proposed, except for some special cases. We present a polynomial algorithm with a tight approximation ratio of $$\max \left\{ \frac{3}{2},2-\frac{1}{k}\right\} $$ for arbitrary $$k\geqslant 1$$ , and an algorithm with approximation ratio $$\frac{5}{3}$$ that runs in polynomial time for fixed k. Moreover, we develop a recursive framework to improve the approximation ratio to $$\frac{3}{2}+\epsilon $$ . This framework is polynomial for fixed k and $$\epsilon $$ , and may be useful in improving the Christofides-like heuristics for other related multiple salesmen routing problems.