On Packing Two-Dimensional Bins

Suppose we are given a set L of rectangular items and wish to pack them into identical rectangular bins, so that no two items overlap and so that the number of bins used is minimized. This generalization of the standard one-dimensional bin packing problem models problems arising in a variety of applications, from truck loading to the design of VLSI chips. We propose a hybrid algorithm, based on algorithms for simpler bin packing problems, and show that proof techniques developed for the simpler cases can be combined to prove close bounds on the worst case behavior of the new hybrid. These are the first such close bounds obtained for this problem.