- INSTANCE:
Set of rectangles
with positive sizes (width
and height ).
- SOLUTION:
A packing
*P*of the rectangles in*B*into a unit-width bin with infinite height. The rectangles must be packed orthogonally and may not be rotated. - MEASURE:
Height of the packing
*P*.

*Good News:*Approximable within 2 [430].*Comment:*Also called*Minimum Strip Packing*. Approximable within in time polynomial in for any [301]. Variation in which the dimensions of the rectangles are bounded below by a constant admits a PTAS [165]. The three-dimensional variation is approximable within 3.25 [356].