Approximation algorithms for multiple terminal, Hamiltonian path problems

摘要

This article presents a new 2-approximation algorithm for a multiple depot, multiple terminal, Hamiltonian path problem when the costs satisfy the triangle inequality. For the case where all the salesmen start from the same depot, we present another algorithm with an approximation ratio of 5/3 . These results generalize the approximation algorithms currently available for the single depot, single terminal Hamiltonian path problem.