A tale of two dimensional bin packing

The 2-dimensional Bin Packing problem (2BP) is a generalization of the classical Bin Packing problem and is defined as follows: Given a collection of rectangles specified by their width and height, oack: these into minimum number of squares bins of units size. We study the case of "orthogonal packing without rotations", where rectangles cannot be rotated and must be packed parallel to the edges of a bin. Often in practical cases of 2BP problems there are additional constraints on how complicated the packing patterns in a bin can be. A well-studied and frequently used constraint is that every rectangle in the packing must be obtainable by recursively applying a sequence of edge-to-edge cuts parallel to the edge of the bin. Such cuts are known as guillotine cuts. Our main results is that the guillotine 2BP problem admits an asymptotic polynomial time approximation scheme. This is sharp contrast with the fact that the general 2BP problem is APX-Hard. En route to our main result, we show a structural theorem about approximating general guilootine packings by simpler packings, which could be of independent interest.