5/3-Approximation Algorithm for a Multiple Depot, Terminal Hamiltonian Path Problem

Rathinam Sivakumar and Raja Sengupta

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

Abstract: Though 2-approximation algorithms are available for several Multiple Depot Travelling Salesman Problems (TSPs)and Hamiltonian Path Problems (HPPs), there are no algorithms in the literature for any multiple depot variant of TSP or HPP that has an approximation ratio better than 2. This paper addresses one variant of the Multiple Depot HPP and provides the first 5/3-approximation algorithm for the same when the costs are symmetric and satisfy triangle inequality.

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

Downloads: (external link)
https://www.escholarship.org/uc/item/3dw086dn.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:qt3dw086dn

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 ().