Algorithms for Packing Squares: A Probabilistic Analysis

Authors:

Abstract
This paper gives a probabilistic performance analysis of simple algorithms for packing lists $L_n $, 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 ${\operatorname{OPT}}(L_n)$ denote the height of an optimal strip packing for list $L_n $. A simple $O(n\log n)$ approximation algorithm, called Algorithm A, is described and it is proven that the height $A(L_n )$ of a packing of list $L_n $ satisfies $A(L_n ) - {\operatorname{OPT}}(L_n ) \leqq \tfrac{1}{4}$ with probability $1 - O(e^{ - c_0 n} )$ for a positive constant $c_0 $. It is also shown that $E[{\operatorname{OPT}}(L_n )] = 3n/8 + \Theta (n^{{1 / 3}} )$. The bin-packing problem is to pack the squares into square bins of size 1 so as to minimize the number of bins. Let ${\operatorname{OPT}}_B (L_n )$ denote the number of bins in an optimal packing of list $L_n $. The authors present another $O(n\log n)$ approximation algorithm and show that the number of bins it needs to pack a list $L_n $ is precisely ${\operatorname{OPT}}_B (L_n )$ with probability $1 - O(e^{ - c_1 n} )$ for a positive constant $c_1 $. Finally, it is shown that $E[{\operatorname{OPT}}_B (L_n )] = {n / 2} + \Theta (1)$. These bounds for packing squares into strips and bins are much tighter than GTthose that have been obtained for packing rectangles.