MINIMUM HEIGHT TWO DIMENSIONAL PACKING

• INSTANCE: Set of rectangles $B=\{(x_i,y_i)\}$ with positive sizes (width $x_i \leq 1$ and height $y_i$).

• 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 $1+\varepsilon +O(\max y_i/\varepsilon ^2)/\mbox{\sl opt}$ in time polynomial in $1/\varepsilon$ for any $\varepsilon >0$ [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].