Next: MAXIMUM D-VECTOR COVERING Up: Data Storage Previous: MINIMUM BIN PACKING Index

### MINIMUM HEIGHT TWO DIMENSIONAL PACKING

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