Algorithms for packing squares: A probabilistic analysis

This paper gives a probabilistic performance analysis of simple algorithms for packing lists Ln of n squares into a strip or a set of bins. It is assumed that the square sizes are drawn independently from the uniform distribution on [0, 1]. The strip-packing problem is to pack the squares into a strip of width 1 so as to minimize the height of the packing. Let denote the height of an optimal strip packing for list Ln . A simple approximation algorithm, called Algorithm A, is described and it is proven that the height of a packing of list L n satisfies with probability for a positive constant c 0. It is also shown that . The bin-packing problem is to pack the squares into square bins of size 1 so as to minimize the number of bins. Let denote the number of bins in an optimal packing of list Ln. The authors present another approximation algorithm and show that the number of bins it needs to pack a list Ln is precisely with probability for a positive constant c1. Finally, it is shown that . These bounds for packing squares into strips and bins are much tighter than those that have been obtained for packing rectangles.