Approximation algorithms for multiple terminal, Hamiltonian path problems
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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. 2010 Springer-Verlag.