Approximation algorithms for multiple terminal, Hamiltonian path problems Academic Article

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.

authors

• Rathinam, Sivakumar

published proceedings

• OPTIMIZATION LETTERS

author list (cited authors)

• Bae, J., & Rathinam, S.

citation count

• 9

complete list of authors

• Bae, Jungyun||Rathinam, Sivakumar

publication date

• January 2012

publisher

• Springer Nature  Publisher

published in

• Optimization Letters  Journal

keywords

• Approximation Algorithms
• Hamiltonian Path Problem
• Traveling Salesman Problem

Digital Object Identifier (DOI)

• 10.1007/s11590-010-0252-4

start page

• 69

end page

• 85

volume

• 6

issue

• 1

URL

• http://dx.doi.org/10.1007/s11590-010-0252-4