Approximating the multiple-depot multiple-terminal Hamiltonian path problem

In this paper, we study a multiple-terminal extension of the classic Hamiltonian path problem where $m$ salesmen are initially located at different depots and finally stopped at different terminals. To the best of our knowledge, only 2-approximation algorithm is available in the literature. For arbitrary $m?2$, we first present a Christofides-like heuristic with a tight approximation ratio of $2?\frac{1}{2m+1}$. Besides, we also develop a $(\frac{5}{3}+?)$-approximation algorithm by divide-and-conquer technique. The $(\frac{5}{3}+?)$-approximation algorithm runs in polynomial time for fixed $m$ and $?$.