Next: MAXIMUM D-VECTOR COVERING
Up: Data Storage
Previous: MINIMUM BIN PACKING
  Index
- INSTANCE:
Set of rectangles
with positive sizes (width
and height yi).
- 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 [407].
- Comment:
Also called Minimum Strip Packing.
Approximable within
in time
polynomial in
for any
[286].
Variation in which the dimensions of the rectangles are
bounded below by a constant admits a PTAS [152].
The three-dimensional variation is approximable within 3.25 [338].
Viggo Kann
1999-04-22