A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
复制标题
平面图中有限容量车辆路径的 PTAS
DOI：
10.1007/978-3-030-24766-9_8
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Schild, Aaron
中科院分区：
文献类型：
--
作者：
Becker, Amariah;Klein, Philip N;Schild, Aaron
有能力的车辆调度问题是找到一个最小成本的图尔斯，共同涵盖客户端在一个图中，这样，每个旅游开始和结束在一个指定的仓库，并受到一个能力上的客户端，它可以服务的数量。在本文中，我们提出了一个多项式时间近似计划（PTAS）的情况下，输入图是平面的，容量是有界的。以前，对于这些情况，只知道准多项式时间近似方案。为了获得这一结果，我们展示了如何将平面图嵌入到有界树宽图中，同时保持预期的客户端到客户端的距离，直到一个与客户端到仓库的距离成比例的小的附加误差。
TheCapacitated Vehicle Routingproblem is to find a minimum-cost set of tours that collectively cover clients in a graph, such that each tour starts and ends at a specified depot and is subject to a capacity bound on the number of clients it can serve. In this paper, we present a polynomial-time approximation scheme (PTAS) for instances in which the input graph is planar and the capacity is bounded. Previously, only a quasipolynomial-time approximation scheme was known for these instances. To obtain this result, we show how to embed planar graphs into bounded-treewidth graphs while preserving, in expectation, the client-to-client distances up to a small additive error proportional to client distances to the depot.
登录
查看更多内容
有界公路维度中 k 中心、k 中值和容量车辆路线的多项式时间近似方案
影响因子：
3.7
作者：
Amariah Becker;P. Klein;David Saulpic
通讯作者：
David Saulpic
平面有界图上车辆路径的拟多项式时间逼近方案
影响因子：
3.7
作者：
Amariah Becker;P. Klein;David Saulpic
通讯作者：
David Saulpic
将平面图嵌入到低树宽图中，并应用于度量问题的高效近似方案
DOI：
10.1137/1.9781611975482.66
发表时间：
2019
期刊：
Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete Algorithms
影响因子：
--
作者：
Eli Fox-Epstein, Eli
Klein
通讯作者：
Eli Fox-Epstein, Eli
Klein
R^d 中欧几里得容量车辆路径问题的 PTAS
影响因子：
3.7
作者：
M. Khachay;R. Dubinin
通讯作者：
R. Dubinin
A (1+ε)-将低公路维数图嵌入有界树宽图
影响因子：
3.7
作者：
A. Feldmann;W. Fung;J. Könemann;Ian Post
通讯作者：
Ian Post