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

Sivakumar Rathinam and Raja Sengupta

Institute of Transportation Studies, Research Reports, Working Papers, Proceedings from Institute of Transportation Studies, UC Berkeley

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.

Keywords: Engineering; Logistics (search for similar items in EconPapers)
Date: 2007-10-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.escholarship.org/uc/item/06p2815q.pdf;origin=repeccitec (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cdl:itsrrp:qt06p2815q

Access Statistics for this paper

More papers in Institute of Transportation Studies, Research Reports, Working Papers, Proceedings from Institute of Transportation Studies, UC Berkeley Contact information at EDIRC.
Bibliographic data for series maintained by Lisa Schiff ().