Abstract
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 utov distance is preserved up to an additive error of epsilon times the utoroot plus vtoroot distances. We show that this embedding yields a PTAS for BoundedCapacity 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 depottodepot 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 BoundedCapacity 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 kCenter 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 kMedian in graphs of bounded highway dimension. In this problem, the goal is to minimize the sum of distances to the k centers.
BibTeX  Entry
@InProceedings{becker_et_al:LIPIcs:2018:9471,
author = {Amariah Becker and Philip N. Klein and David Saulpic},
title = {{PolynomialTime Approximation Schemes for kcenter, kmedian, and Capacitated Vehicle Routing in Bounded Highway Dimension}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {8:18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9471},
URN = {urn:nbn:de:0030drops94710},
doi = {10.4230/LIPIcs.ESA.2018.8},
annote = {Keywords: Highway Dimension, Capacitated Vehicle Routing, Graph Embeddings}
}
Keywords: 

Highway Dimension, Capacitated Vehicle Routing, Graph Embeddings 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018) 
Issue Date: 

2018 
Date of publication: 

08.08.2018 