An approximation scheme for strip packing of rectangles with bounded dimensions Original Research Article

It is shown that for any positive ε the strip-packing problem, i.e. the problem of packing a given list of rectangles into a strip of width 1 and minimum height, can be solved within 1 + ε times the optimal height, in linear time, if the heights and widths of these rectangles are all bounded below by an absolute constant δ > 0.