Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorHassin, Refael
dc.date.accessioned2009-10-02T12:19:09Z
dc.date.available2009-10-02T12:19:09Z
dc.date.issued2005
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2080
dc.language.isoenen
dc.subjectApproximation algorithm
dc.subjectVRP
dc.subjectDifferential ratio
dc.subjectTSP
dc.subject.ddc511en
dc.titleApproximation algorithms for some vehicle routing problems
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDepartment of Statistics and Operations Research Tel-Aviv University;Israël
dc.description.abstractenWe study vehicle routing problems with constraints on the distance traveled by each vehicle or on the number of vehicles. The objective is either to minimize the total distance traveled by vehicles or to minimize the number of vehicles used. We design constant differential approximation algorithms for kVRP. Note that, using the differential bound for METRIC 3VRP, we obtain the randomized standard ratio<> This is an improvement of the best-known bound of 2 given by Haimovich et al. (Vehicle Routing Methods and Studies, Golden, Assad, editors, Elsevier, Amsterdam, 1988). For natural generalizations of this problem, called EDGE COST VRP, VERTEX COST VRP, MIN VEHICLE and kTSP we obtain constant differential approximation algorithms and we show that these problems have no differential approximation scheme, unless P=NP.
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol146
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2005
dc.relation.isversionofjnlpages27-42
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2004.07.003
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-05T14:47:35Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record