A Structural Lemma in 2-Dimensional Packing, and Its Applications on Approximability

We present a new lemma stating that, given an arbitrary packing of a set rectangles into a larger rectangle, a “structured” packing of nearly the same set of rectangles exists. This lemma seems to have several potential implications on the approximability of 2-dimensional packing problems. In this paper, we use it to show the existence of a polynomial-time approximation scheme for 2-dimensional knapsack in case the range of the profit over area ratios 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, whose existence was open. For general 2-dimensional knapsack, the best approximation guarantee known to be achievable in polynomial time is arbitrarily close to 2, and the existence of a polynomial-time approximation scheme remains open. Moreover, we show that our approximation scheme can be used as an approximate separation oracle for 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. By the equivalence between approximate separation and optimization, this implies the existence of a(n asymptotic) polynomial-time approximation scheme for 2-dimensional fractional bin packing itself, which in turn has implications on the approximability of 2-dimensional bin packing. An interesting aspect of this last result is the fact that, in order to derive it, we have to change the customary set covering formulation (introducing upper bounds on the dual LP variables to define a modified LP which is almost equivalent) since we know how to solve approximately the column generation problem only after the change.