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-1/2m+1. Besides, we also develop a (5/4 + epsilon)-approximation algorithm by divide-and-conquer technique. The (5/4 + epsilon) -approximation algorithm runs in polynomial time for fixed m and E. (C) 2019 Elsevier B.V. All rights reserved.