Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Mathieu, Claire; Zhou, Hang https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-164369
URL:

;

A PTAS for Capacitated Vehicle Routing on Trees

pdf-format:


Abstract

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.

BibTeX - Entry

@InProceedings{mathieu_et_al:LIPIcs.ICALP.2022.95,
  author =	{Mathieu, Claire and Zhou, Hang},
  title =	{{A PTAS for Capacitated Vehicle Routing on Trees}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16436},
  URN =		{urn:nbn:de:0030-drops-164369},
  doi =		{10.4230/LIPIcs.ICALP.2022.95},
  annote =	{Keywords: approximation algorithms, capacitated vehicle routing, graph algorithms, combinatorial optimization}
}

Keywords: approximation algorithms, capacitated vehicle routing, graph algorithms, combinatorial optimization
Seminar: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue date: 2022
Date of publication: 28.06.2022


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI