2026-07-23T15:38:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16436 2024-03-06T10:57:29Z ddc:004 open_access

A PTAS for Capacitated Vehicle Routing on Trees Mathieu, Claire Zhou, Hang approximation algorithms capacitated vehicle routing graph algorithms combinatorial optimization We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Claire Mathieu and Hang Zhou 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.95 urn:nbn:de:0030-drops-164369 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.95 eng https://creativecommons.org/licenses/by/4.0/legalcode