Probabilistic analysis of shelf algorithms for packing rectangles into a strip

In this paper, we consider algorithms to pack rectangles into a strip. As the main result we present an algorithm that packs rectangles online and for which the ratio of expected wasted area to expected occupied area tends to zero as the number of rectangles increases.
The research was supported by the Russian Foundation for Basic Research, grants 05–01–00798 and 04–01–00359.