Abstract:
We consider two variants of a 2-depot Hamiltonian path problem and show that they have an algorithm with an approximation ratio of 32 if the costs are symmetric and satisfy the triangle inequality. This improves the 2-approximation algorithm already available for the problem.
Publication date:
January 1, 2010
Publication type:
Journal Article
Citation:
Rathinam, S., & Sengupta, R. (2010). 3/2–approximation algorithm for two variants of a 2-depot Hamiltonian path problem. Operations Research Letters, 38(1), 63–68. https://doi.org/10.1016/j.orl.2009.10.001