An optimal bound for two dimensional bin packing

Bin packing and dynamic allocation problems hold an important place both in theoretical computer science and in practical issues arising in computer applications and operations research. While major analytic advances have been made for the 1-dimension case, optimal results for 2-dimensional problems have been elusive. As a model for analysis of various multidimensional bin packing and cutting stock problems, we consider the following question. Let be an arbitrary finite family of squares of total area at most unity; what is the smallest rectangle into which any such family can be packed without overlap? We answer this with the following optimal result: 1) any unit family can be packed into a rectangle with sides 2/√3 and √2; 2) any other rectangle with this packing property has larger area. The proof of this is rather lengthy and technical. We therefore restrict this presentation to a general discussion of the methods used and an outline of the major cases together with some specific examples.