Next: MAXIMUM D-VECTOR COVERING
Up: Data Storage
Previous: MINIMUM BIN PACKING
Set of rectangles
with positive sizes (width
and height ).
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.
Height of the packing P.
- Good News:
Approximable within 2 .
Also called Minimum Strip Packing.
Variation in which the dimensions of the rectangles are
bounded below by a constant admits a PTAS .
The three-dimensional variation is approximable within 3.25 .