A GENERALIZATION OF A THEOREM OF KLEITMAN AND KRIEGER.

In this paper, we prove that any finite or infinite family of squares with total area at most 1 can be packed into the rectangle with dimensions and that this rectangle is unique with this property and minimum area. Furthermore, we show that for a finite unit family of n squares which are given sorted by their side lengths, a packing into the rectangle can be found in linear time, which yields an O(n n) time algorithm for the general case. With a restriction to finite unit families, the former statement has been published by D. J. Kleitman and M. Krieger, who - as they state themselves - only provide "a general discussion of the methods used [throughout the proof] and an outline of the major cases". Although they refer their proof to as "being constructive", it is not clear from their presentation how a packing algorithm would look like. Regarding the fact that there are some other results that rely on this statement - some of which even make use of a corresponding packing algorithm - it is important to have an complete and preferably constructive published proof for it. The proof that is presented here is constructive and uses an interesting technique based on quadratic programming which could be applicable to other packing problems as well. [ABSTRACT FROM AUTHOR]