High Multiplicity Strip Packing

An instance of the two-dimensional strip packing problem is specified by n rectangular items, each having a width, 0 \u3c wn ≤ 1, and height, 0 \u3c hn ≤ 1. The objective is to place these items into a strip of width 1, without rotations, such that they are nonoverlapping and the total height of the resulting packing is minimized. In this thesis, we consider the version of the two-dimensional strip packing problem where there is a constant number K of distinct rectangle sizes and present an OPT + K - 1 polynomial-time approximation algorithm for it. This beats a previous algorithm with a worst case bound of OPT + K; the time complexity of that algorithm was not known and here we show that it runs in polynomial time