2026-07-24T09:31:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9471 2024-03-06T10:43:49Z ddc:004 open_access

Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension Becker, Amariah Klein, Philip N. Saulpic, David Highway Dimension Capacitated Vehicle Routing Graph Embeddings The concept of bounded highway dimension was developed to capture observed properties of road networks. We show that a graph of bounded highway dimension with a distinguished root vertex can be embedded into a graph of bounded treewidth in such a way that u-to-v distance is preserved up to an additive error of epsilon times the u-to-root plus v-to-root distances. We show that this embedding yields a PTAS for Bounded-Capacity Vehicle Routing in graphs of bounded highway dimension. In this problem, the input specifies a depot and a set of clients, each with a location and demand; the output is a set of depot-to-depot tours, where each client is visited by some tour and each tour covers at most Q units of client demand. Our PTAS can be extended to handle penalties for unvisited clients. We extend this embedding result to handle a set S of root vertices. This result implies a PTAS for Multiple Depot Bounded-Capacity Vehicle Routing: the tours can go from one depot to another. The embedding result also implies that, for fixed k, there is a PTAS for k-Center in graphs of bounded highway dimension. In this problem, the goal is to minimize d so that there exist k vertices (the centers) such that every vertex is within distance d of some center. Similarly, for fixed k, there is a PTAS for k-Median in graphs of bounded highway dimension. In this problem, the goal is to minimize the sum of distances to the k centers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amariah Becker and Philip N. Klein and David Saulpic 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.8 urn:nbn:de:0030-drops-94710 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.8 eng https://creativecommons.org/licenses/by/3.0/legalcode