Improved Approximation Algorithm for Two-Dimensional Bin Packing
Improved Approximation Algorithm for Two-Dimensional Bin Packing
复制标题
改进的二维装箱近似算法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Khan
中科院分区：
文献类型：
--
作者：
N. Bansal;A. Khan
本文研究了带旋转和不带旋转的二维装箱问题。在这里，我们给出了一组二维矩形项I，目标是将这些项装入最小数量的单位正方形箱中。我们考虑的正交包装的情况下，物品的边缘必须对齐平行的边缘的bin。我们的主要结果是一个1.405近似的二维装箱旋转和不旋转，这改善了最近的1.5近似由于詹森和Pradel。我们还表明，一个广泛的类的舍入算法不能提高1.5的因素。
We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Pradel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5.