论文标题
关于减少动态矢量箱包装的数据
On data reduction for dynamic vector bin packing
论文作者
论文摘要
我们研究动态矢量箱填料（DVBP）问题。我们表明，将任意DVBP实例缩小到请求类型的数量或最大请求数量重叠的请求数量中的尺寸多项式。我们还提供了一种简单的多项式数据缩减算法，该算法允许恢复$（1 + {\ varepsilon}）$ - 任意$ {\ varepsilon}> 0 $的近似解决方案。它通过$ {\ varepsilon} = 0.02 $的数量级从Microsoft Azure和Huawei Cloud缩小实例。
We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal number of requests overlapping in time. We also present a simple polynomial-time data reduction algorithm that allows to recover $(1 + {\varepsilon})$-approximate solutions for arbitrary ${\varepsilon} > 0$. It shrinks instances from Microsoft Azure and Huawei Cloud by an order of magnitude for ${\varepsilon} = 0.02$.
