SR2 M INIMUM H EIGHT T WO D IMENSIONAL P ACKING

     
• I NSTANCE : Set of rectangles with positive sizes (width and height ).
• S OLUTION : 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.
• M EASURE : Height of the packing P .

• Good News: Approximable within 2 [ 316 ].
• Comment: Also called Minimum Strip Packing .     Approximable within in time polynomial in for any [ 214 ]. Variation in which the dimensions of the rectangles are bounded below by a constant admits a PTAS [ 108 ]. The three-dimensional variation is approximable within 3.25 [ 256 ].