A Structural Lemma in 2-Dimensional Packing, and its Implications on Approximability

We present a new lemma stating that, given an arbitrary packing of a set of rectangles into a larger rectangle, a “structured” packing of nearly the same set of rectangles exists. In this paper, we use it to show the existence of a polynomial-time approximation scheme for 2-dimensional geometric knapsack in the case where the range of the profit to area ratio of the rectangles is bounded by a constant. As a corollary, we get an approximation scheme for the problem of packing rectangles into a larger rectangle to occupy the maximum area. Moreover, we show that our approximation scheme can be used to find a (1 + ε)-approximate solution to 2-dimensional fractional bin packing, the LP relaxation of the popular set covering formulation of 2-dimensional bin packing, which is the key to the practical solution of the problem.