Approximation Algorithms for 3D Orthogonal Knapsack
Approximation Algorithms for 3D Orthogonal Knapsack
复制标题
3D正交背包的逼近算法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
H. Thomas
中科院分区：
文献类型：
--
作者：
Florian Diedrich;Rolf Harren;K. Jansen;Ralf Thöle;H. Thomas
我们研究了具有利润的三维盒子的非重叠轴平行包装成一个专用的更大的盒子，其中禁止或允许旋转，我们希望最大化总利润。由于这个优化问题是np困难的，我们关注的是近似算法。我们获得了近似比为9 +柱和8 +柱的非旋转场景的快速简单算法，以及近似比为7 +柱的算法，该算法使用更复杂的技术；这是已知的这个问题的最小近似比。此外，我们展示了所使用的技术如何适用于允许绕z轴或绕所有轴旋转90°的情况，在这种情况下，我们分别获得近似比为6 + λ和5 + λ的算法。最后，我们的方法得到了一个可包装性准则的三维推广和一个绝对近似比为29/4的条形包装算法，改进了之前已知的45/4的结果。
We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 + ϵ and 8 + ϵ, as well as an algorithm with approximation ratio 7 + ϵ that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 + ϵ and 5 + ϵ, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.