dc.contributor.author | Charikar, Moses | en_US |
dc.contributor.author | Khuller, Samir | en_US |
dc.contributor.author | Raghavachari, Balaji | en_US |
dc.date.accessioned | 2004-05-31T22:48:30Z | |
dc.date.available | 2004-05-31T22:48:30Z | |
dc.date.created | 1997-11 | en_US |
dc.date.issued | 1998-10-15 | en_US |
dc.identifier.uri | http://hdl.handle.net/1903/923 | |
dc.description.abstract | Given $n$ identical objects (pegs), placed at arbitrary initial
locations, we consider the problem of transporting them efficiently to
$n$ target locations (slots) with a vehicle that can carry at most $k$
pegs at a time. This problem is referred to as $k$-delivery TSP, and
it is a generalization of the Traveling Salesman Problem.
We give a 5-approximation algorithm for the problem of minimizing the
total distance traveled by the vehicle.
There are two kinds of transportations possible --- one that could
drop pegs at intermediate locations and pick them up later in the
route for delivery (preemptive) and one that transports pegs to their targets
directly (non-preemptive).
In the former case, by exploiting the freedom to drop, one
may be able to find a shorter delivery route.
We construct a non-preemptive tour that is within a factor 5
of the optimal preemptive tour.
In addition we show that the ratio
of the distances traveled by an optimal non-preemptive tour versus a
preemptive tour is bounded by 4.
(Also cross-referenced as UMIACS-TR-97-79) | en_US |
dc.format.extent | 270486 bytes | |
dc.format.mimetype | application/postscript | |
dc.language.iso | en_US | |
dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3847 | en_US |
dc.relation.ispartofseries | UMIACS; UMIACS-TR-97-79 | en_US |
dc.title | Algorithms for Capacitated Vehicle Routing | en_US |
dc.type | Technical Report | en_US |
dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |