2-DIMENSIONAL RECTANGLE PACKING - ONLINE METHODS AND RESULTS

被引：19

作者：

CSIRIK, J

FRENK, JBG

LABBE, M

机构：

[1] Econometrisch Instituut, Erasmus Universiteit Rotterdam, 3000 DR Rotterdam

来源：

DISCRETE APPLIED MATHEMATICS | 1993年 / 45卷 / 03期

关键词：

D O I：

10.1016/0166-218X(93)90009-D

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The first algorithms for the on-line two-dimensional rectangle packing problem were introduced by Coppersmith and Raghavan. They showed that for a family of heuristics 13/4 is an upper bound for the asymptotic worst-case ratios. We have investigated the Next Fit and the First Fit variants of their method. We proved that the asymptotic worst-case ratio equals 13/4 for the Next Fit variant and that 49/16 is an upper bound of the asymptotic worst-case ratio for the First Fit variant.

引用

页码：197 / 204

页数：8

共 6 条

[1] ON PACKING TWO-DIMENSIONAL BINS [J].