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

Simple item page
dc.creatorDas, Aparna
dc.creatorMathieu, Claire
dc.date2008-12-08
dc.date.accessioned2026-07-07T12:10:43Z
dc.date.available2026-07-07T12:10:43Z
dc.descriptionIn 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.
dc.identifierhttps://arxiv.org/abs/0812.1595
dc.identifierhttp://arxiv.org/abs/0812.1595
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/210014
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.titleA quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing
dc.typetext

Files

Collections

arXiv