Abstract:
We consider a Generalized, Multiple Depot Hamiltonian Path Problem (GMDHPP) and show that it has an algorithm with an approximation ratio of 3/2 if the costs are symmetric and satisfy the triangle inequality. This improves on the 2-approximation algorithm already available for the same.
Publication date:
October 1, 2007
Publication type:
Research Report
Citation:
Rathinam, S., & Sengupta, R. (2007). 3/2-Approximation Algorithm for a Generalized, Multiple Depot, Hamiltonian Path Problem. https://escholarship.org/uc/item/06p2815q