论文标题
将D维数字包装成垃圾箱包装的谐波算法
Harmonic Algorithms for Packing d-dimensional Cuboids Into Bins
论文作者
论文摘要
我们探索了$ D $二维几何垃圾箱包装问题（$ d $ bp）的近似算法。 Caprara（MOR 2008）给出了一种基于谐波的算法，用于$ d $ bp，其渐近近似值（AAR）为$ t _ {\ infty}^{d-1} $（其中$ t _ {\ infty} \ and）。但是，它们的算法不允许旋转项目。这与$ d $ bp的一些常见应用相反，例如将盒子打包到运输容器中。当物品可以正交围绕全部或一个子集轴旋转时，我们给出$ d $ bp的近似算法。我们首先给出具有aar $ t _ {\ infty}^{d} $的快速而简单的基于谐波的算法。接下来，我们给出了一个更复杂的基于谐波的算法，我们称其为$ \ mathtt {hgap} _k $，具有aar $ t _ {\ infty}^{d-1}（1+ε）$。对于3bp，旋转的AAR大约为2.860 +ε$，这在最著名的AAR上提高了$ 4.5 $。 此外，我们研究了概括旋转情况的多项选择箱填料问题。在这里，我们得到了$ n $的$ d $二维立方体物品，我们必须从每组中选择一个项目，然后打包所选的物品。我们的算法也适用于多项选择垃圾箱包装问题。我们还为$ d $ d带包装的多项选择版本和$ d $ d $ d的几何背包提供了快速而简单的近似算法。
We explore approximation algorithms for the $d$-dimensional geometric bin packing problem ($d$BP). Caprara (MOR 2008) gave a harmonic-based algorithm for $d$BP having an asymptotic approximation ratio (AAR) of $T_{\infty}^{d-1}$ (where $T_{\infty} \approx 1.691$). However, their algorithm doesn't allow items to be rotated. This is in contrast to some common applications of $d$BP, like packing boxes into shipping containers. We give approximation algorithms for $d$BP when items can be orthogonally rotated about all or a subset of axes. We first give a fast and simple harmonic-based algorithm having AAR $T_{\infty}^{d}$. We next give a more sophisticated harmonic-based algorithm, which we call $\mathtt{HGaP}_k$, having AAR $T_{\infty}^{d-1}(1+ε)$. This gives an AAR of roughly $2.860 + ε$ for 3BP with rotations, which improves upon the best-known AAR of $4.5$. In addition, we study the multiple-choice bin packing problem that generalizes the rotational case. Here we are given $n$ sets of $d$-dimensional cuboidal items and we have to choose exactly one item from each set and then pack the chosen items. Our algorithms also work for the multiple-choice bin packing problem. We also give fast and simple approximation algorithms for the multiple-choice versions of $d$D strip packing and $d$D geometric knapsack.
