Probabilistic analysis of a new strip packing algorithm

Abstract

In 1993 Coffman and Shor proposed on-line strip packing algorithm with expected unpacked area (waste area) of order O(n^{2/3}) in a standard probabilistic model, where n is the number of rectangles. In the standard probabilistic model the width and height of each rectangle are independent random variables with uniform distribution in [0,1]. It is well-known that optimal packing  has expected waste of order O(n^{1/2}) and there exists off-line polynomial algorithm that provides this bound. During more than 10 years the question concerning the possibility to obtain similar upper bound in the class of on-line packing algorithms was open. It was also known that in the class of popular so-called shelf algorithms the bound O(n^{2/3}) cannot be improved. In this paper we give positive answer to this question. We analyze new packing algorithm proposed recently by the author and prove new upper bound of unpacked area of order O(n^{1/2} (log n)^{3/2}) which is almost optimal up to logarithmic factor.  The only restriction is the following: we must know the number n of rectangles in advance (exactly as in algorithm of Coffman and Shor). In a popular terminology concerning on-line algorithms this means that our algorithm is closed-end on-line algorithm.