3/2-approximation algorithm for two variants of a 2-depot Hamiltonian path problem Academic Article

abstract

• We consider two variants of a 2-depot Hamiltonian path problem and show that they have an algorithm with an approximation ratio of frac(3, 2) if the costs are symmetric and satisfy the triangle inequality. This improves the 2-approximation algorithm already available for the problem. 2009 Elsevier B.V. All rights reserved.

authors

• Rathinam, Sivakumar

published proceedings

• OPERATIONS RESEARCH LETTERS

author list (cited authors)

• Rathinam, S., & Sengupta, R.

citation count

• 17

complete list of authors

• Rathinam, Sivakumar||Sengupta, Raja

publication date

• January 2010

publisher

• Elsevier  Publisher

published in

• Operations Research Letters  Journal

keywords

• Approximation Algorithms
• Hamiltonian Path Problem
• Traveling Salesman Problem

Digital Object Identifier (DOI)

• 10.1016/j.orl.2009.10.001

start page

• 63

end page

• 68

volume

• 38

issue

• 1

URL

• http://dx.doi.org/10.1016/j.orl.2009.10.001