Abstract:
The problem of packing rectangles into several strips is considered. It is shown that for this problem there exist on-line algorithms with multiplicative error asymptotically close to $2e$, where $e$ is the base of the natural logarithm. It is proved that none of the on-line algorithms can have the asymptotic multiplicative error less than $e$.