We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in the two-dimensional plane and the goal is to pack them in a vertical strip of a fixed width such that the height of the obtained packing is minimized. The packing must be non-overlapping and the rectangles cannot be rotated. A reduction from the partition problem shows that no approximation better than 3 2 is possible for strip packing in polynomial time (assuming P @math NP). Nadiradze and Wiese [SODA16] overcame this barrier by presenting a @math -approximation algorithm in pseudo-polynomial-time (PPT). As the problem is strongly NP-hard, it does not admit an exact PPT algorithm. In this paper, we make further progress on the PPT approximability of strip packing, by presenting a @math -approximation algorithm. Our result is based on a non-trivial repacking of some rectangles in the left by the construction by Nadiradze and Wiese, and in some sense pushes their approach to its limit. Our PPT algorithm can be adapted to the case where we are allowed to rotate the rectangles by @math , achieving the same approximation factor and breaking the polynomial-time approximation barrier of 3 2 for the case with rotations as well.
Strip packing has also been well studied for higher dimensions. The present best asymptotic approximation for 3-D strip packing is due to Jansen and Pr " a del @cite_33 who presented a 1.5-approximation extending techniques from 2-D bin packing.
@cite_33
2013696768 54707646 2060963575 2098666887
We present an asymptotic (2 + e)-approximation algorithm for the 3D-strip packing problem, for any e > 0. In the 3D-strip packing problem the input is a set L = b 1 , b 2 ,. . ., b n of 3-dimensional boxes. Each box b i has width, length, and height at most 1. The problem is to pack the boxes into a 3-dimensional bin B of width 1, length 1 and minimum height, so that the boxes do not overlap. We consider here only orthogonal packings without rotations; this means that the boxes are packed so that their faces are parallel to the faces of the bin, and rotations are not allowed. This algorithm improves on the previously best algorithm of Miyazawa and Wakabayashi which has asymptotic performance ratio of 2.64. Our algorithm can be easily modified to a (4 + e)-approximation algorithm for the 3D-bin packing problem. We study the 3-dimensional Strip Packing problem: Given a list of n boxes b 1,…,b n of the width w i ≤ 1, depth d i ≤ 1 and an arbitrary length l i . The objective is to pack all boxes into a strip of the width and depth 1 and infinite length, so that the packing length is minimized. The boxes may not overlap or be rotated. We present an improvement of the current best asymptotic approximation ratio of 1.692 by [2] with an asymptotic 3 2 + e-approximation for any e > 0. We present an asymptotic fully polynomial approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classicalNP-hard cutting-stock problem. The algorithm, based on a new linear-programming relaxation, finds a packing ofn rectangles whose total height is within a factor of (1 +e) of optimal (up to an additive term), and has running time polynomial both in n and in 1 e. We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations into a strip of width 1 and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of 5 3+@e for any @e>0. This result significantly narrows the gap between the best known upper bound and the lower bound of 3 2; previously, the best upper bound was 1.9396 due to Harren and van Stee.