论文标题
用于树木上距离约束的车辆路由的近似算法
An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees
论文作者
论文摘要
在受距离约束的车辆路由问题（DVRP）中，我们获得了一个带有整数边缘权重，仓库，一组$ n $终端和距离约束$ d $的图形。目的是在仓库中找到最少的旅行开始和结束，以便这些游览涵盖所有航站楼，每个旅行的长度最多为$ d $。 树上的DVRP引起了独立的兴趣，因为它等同于Sindelar等人研究的树上的虚拟机填料问题。 [SPAA'11]。我们为树dvrp设计了一种简单自然的近似算法，由$ \ varepsilon> 0 $参数化。我们表明，其近似值为$α+ \ varepsilon $，其中$α\约1.691 $，此外，我们的分析基本上是紧密的。运行时间是$ n $和$ d $的多项式。由于Nagarajan和Ravi [Networks'12]，近似值的比率提高了2。 本文的主要新颖性在于算法的分析。它依赖于从树DVRP减少到有限的在线垃圾箱包装问题，这是通过新的长度概念。
In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of $n$ terminals, and a distance constraint $D$. The goal is to find a minimum number of tours starting and ending at the depot such that those tours together cover all the terminals and the length of each tour is at most $D$. The DVRP on trees is of independent interest, because it is equivalent to the virtual machine packing problem on trees studied by Sindelar et al. [SPAA'11]. We design a simple and natural approximation algorithm for the tree DVRP, parameterized by $\varepsilon >0$. We show that its approximation ratio is $α+ \varepsilon$, where $α\approx 1.691$, and in addition, that our analysis is essentially tight. The running time is polynomial in $n$ and $D$. The approximation ratio improves on the ratio of 2 due to Nagarajan and Ravi [Networks'12]. The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction from the tree DVRP to the bounded space online bin packing problem via a new notion of reduced length.
