Cover Image

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

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.
Year of publication:
2007-05-01
Authors: Sivakumar, Rathinam ; 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/10010536953
Similar items by subject
Similar items by person