A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing

Details A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing

2008-12-08

arxiv.org/abs/0812.1595v1

Computer Science

Discrete Mathematics

Scientific paper

In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.

Affiliated with

Also associated with

No associations

Rating

A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-281619