Skip to main content
eScholarship
Open Access Publications from the University of California

3/2-Approximation Algorithm for a Generalized, Multiple Depot, Hamiltonina Path Problem

  • Author(s): Rathinam, Sivakumar
  • Sengupta, Raja
  • et al.
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.

Main Content
Current View