An optimal bound for two dimensional bin packing

1 October 1975

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 163-168
https://doi.org/10.1109/sfcs.1975.6

Abstract

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.

Keywords

This publication has 5 references indexed in Scilit:

On Packing Squares with Equal Squares
Published by Defense Technical Information Center (DTIC) ,1975
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
SIAM Journal on Computing, 1974
Worst-case analysis of memory allocation algorithms
Published by Association for Computing Machinery (ACM) ,1972
Packing Squares in Rectangles I
Annals of the New York Academy of Sciences, 1970
On packing of squares and cubes
Journal of Combinatorial Theory, 1968