Cover Image

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

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.
Year of publication:
2007-10-01
Authors: Rathinam, Sivakumar ; Sengupta, Raja
Institutions: Institute for Transportation Studies (ITS), University of California-Berkeley
Subject: Logistics
Extent:
application/pdf
Series:
Type of publication: Book / Working Paper
Notes:
The text is part of a series Institute of Transportation Studies (UCB)
Source:
Persistent link: https://www.econbiz.de/10010817559
Similar items by subject
Similar items by person