Approximation Algorithms for 3D Orthogonal Knapsack

Florian、Diedrich、Rolf、Harren、Klaus、Jansen、Ralf、Thoele

2008Acta Scientiarum Naturalium Universitatis SunyatseniEngineering被引 3

摘要

我们与利润学习 3D 盒子的非重叠的轴平行包装进旋转也被禁止或允许的一个奉献更大的盒子，并且我们希望最大化全部的利润。因为这个优化问题是 NP 难的，我们集中于近似算法。我们与近似比率为非旋转的情形获得快、简单的算法 9 + ϵ并且有近似比率 7 + ϵ 的 8 + ϵ ，以及一个算法那使用更复杂的技术；这些是为这个问题知道的最小的近似比率。而且，我们显示出使用的技术怎么能被使适应由在 Z 轴附近或在所有斧子附近的 90 °的旋转被允许的盒子，在我们与近似比率获得算法的地方 6 + ϵ并且 5 + ϵ 分别地。最后，我们的方法与绝对近似比率 29/4 产出一个包装能力标准和一个长带组装算法的 3D 归纳，改进 45/4 的以前最好的已知的结果。

引用本文（GB/T 7714）

Florian, Diedrich, Rolf, 等. Approximation Algorithms for 3D Orthogonal Knapsack[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2008.

引文网络

参考文献与被引分析加载中…

本站仅收录题录与摘要供学习参考，全文版权归属出版方；如有侵权请联系我们删除。