In this paper we study the Multiple Strip Packing (MSP) problem, a generalization of the well-known Strip Packing problem. For a given set of rectangles, r_1,..., r_n, with heights and widths ≤ 1, the goal is to find a non-overlapping orthogonal packing without rotations into k ∈ N strips [0,1] × [0, ∞), minimizing the maximum of the heights. We present an approximation algorithm with absolute ratio 2, which is the best possible, unless P = NP, and an improvement of the previous best result with ratio 2+ε. Furthermore we present simple shelf-based algorithms with short running-time and an AFPTAS for MSP. Since MSP is strongly NP-hard, an FPTAS is ruled out and an AFPTAS is also the best possible result in the sense of approximation theory.
展开▼
