Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
复制标题
DOI：
10.1137/0209062
复制
发表时间：
1980-11
期刊：
影响因子：
--
通讯作者：
E. Coffman;M. Garey;David S. Johnson;R. Tarjan
中科院分区：
文献类型：
--
作者：
E. Coffman;M. Garey;David S. Johnson;R. Tarjan
我们分析了几种“面向水平”的算法，将矩形布局成单位宽度、无限高的箱子，以最小化布局的总高度。对于我们讨论的三种算法，我们证明了该算法得到的高度与最优高度之比是渐近有界的，分别为2、1.7和1.5。后两者大大改善了先前提出的算法的性能界限。此外，对于给定矩形的宽度受限制且仅填充正方形的特殊情况，我们给出了更精细的界。
We analyze several “level-oriented” algorithms for packing rectangles into a unit-width, infinite-height bin so as to minimize the total height of the packing. For the three algorithms we discuss, we show that the ratio of the height obtained by the algorithm to the optimal height is asymptotically bounded, respectively, by 2, 1.7, and 1.5. The latter two improve substantially over the performance bounds for previously proposed algorithms. In addition, we give more refined bounds for special cases in which the widths of the given rectangles are restricted and in which only squares are to be packed.