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.
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].