2026-07-22T20:50:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7878 2024-03-06T10:41:16Z ddc:004 open_access

A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs Becker, Amariah Klein, Philip N. Saulpic, David Capacitated Vehicle Routing Approximation Algorithms Planar Graphs The Capacitated Vehicle Routing problem is a generalization of the Traveling Salesman problem in which a set of clients must be visited by a collection of capacitated tours. Each tour can visit at most Q clients and must start and end at a specified depot. We present the first approximation scheme for Capacitated Vehicle Routing for non-Euclidean metrics. Specifically we give a quasi-polynomial-time approximation scheme for Capacitated Vehicle Routing with fixed capacities on planar graphs. We also show how this result can be extended to bounded-genus graphs and polylogarithmic capacities, as well as to variations of the problem that include multiple depots and charging penalties for unvisited clients. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amariah Becker and Philip N. Klein and David Saulpic 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.12 urn:nbn:de:0030-drops-78781 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.12 eng https://creativecommons.org/licenses/by/3.0/legalcode