Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
复制标题
有界公路维度中 k 中心、k 中值和容量车辆路线的多项式时间近似方案
DOI：
10.4230/lipics.esa.2018.8
复制
发表时间：
2018
影响因子：
3.7
通讯作者：
David Saulpic
中科院分区：
文献类型：
--
作者：
Amariah Becker;P. Klein;David Saulpic
提出了有界公路维度的概念，以获取路网的观测属性。我们证明了具有区别根顶点的有界公路维图可以嵌入到有界树宽的图中，使得u-v距离被保持到epsilon乘以u-根加上v-根距离的加性误差。我们证明了在有界公路维图中，这种嵌入产生了有限容量车辆路径问题的PTAS。在这个问题中，输入指定了一个站点和一组客户，每个客户都有一个位置和需求；输出是一组从站点到站点的线路，其中每个客户被一些线路访问，每个线路最多覆盖客户需求的Q个单位。我们的PTAS可以扩展到处理对未来访客户的处罚。
我们将这一嵌入结果推广到处理一组S根顶点。这一结果暗示了一种多站点有限能力车辆路径的PTAS：路线可以从一个站点到另一个站点。嵌入结果还表明，对于固定的k，在有界公路维图中存在k-中心的PTAS。在这个问题中，目标是最小化d，使得存在k个顶点(中心)，使得每个顶点都在某个中心的距离d内。类似地，对于固定的k，在有界公路维图中存在k-中值的PTAS。在这个问题中，目标是最小化到k个中心的距离之和。
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.