Institute of Transportation Studies at UC Berkeley
3/2-Approximation Algorithm for a Generalized, Multiple Depot, Hamiltonina Path Problem
- Author(s): Rathinam, Sivakumar
- Sengupta, Raja
- et al.
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.