We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height @math , for some arbitrarily small number @math . Our algorithm is polynomial on @math , and thus @math is part of the problem input. For the special case that @math is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height @math using no more than the number of bins in an optimal packing. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. These are the first approximation and resource augmentation schemes for these problems. Our algorithm is based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the @math -norm.
For the 3-dimensional strip packing problem, whose items are boxes, Li and Cheng @cite_28 were the first to present an asymptotic @math -approximation algorithm. Their algorithm was shown to have approximation ratio @math @cite_33 , @math @cite_12 and finally @math @cite_30 . Bansal @cite_23 showed that there is no asymptotic approximation scheme for the rectangle bin packing problem, which implies that there is no APTAS for the 3-dimensional strip packing problem. When the items are cubes, the first specialized algorithm was shown to have asymptotic ratio of @math @cite_28 , and the best result is an asymptotic approximation scheme due to Bansal @cite_30 .
@cite_30 @cite_33 @cite_28 @cite_23 @cite_12
2013696768 2067823599 2060963575 1586863324
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 following packing problem: Given a collection of d-dimensional rectangles of specified sizes, pack them into the minimum number of unit cubes. We show that unlike the one-dimensional case, the two-dimensional packing problem cannot have an asymptotic polynomial time approximation scheme (APTAS), unless PNP. On the positive side, we give an APTAS for the special case of packing d-dimensional cubes into the minimum number of unit cubes. Second, we give a polynomial time algorithm for packing arbitrary two-dimensional rectangles into at most OPT square bins with sides of length 1 , where OPT denotes the minimum number of unit bins required to pack these rectangles. Interestingly, this result has no additive constant term, i.e., is not an asymptotic result. As a corollary, we obtain the first approximation scheme for the problem of placing a collection of rectangles in a minimum-area encasing rectangle. 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 consider the two-dimensional bin packing and strip packing problem, where a list of rectangles has to be packed into a minimal number of rectangular bins or a strip of minimal height, respectively. All packings have to be non-overlapping and orthogonal, i.e., axis-parallel. Our algorithm for strip packing has an absolute approximation ratio of 1.9396 and is the first algorithm to break the approximation ratio of 2 which was established more than a decade ago. Moreover, we present a polynomial time approximation scheme ( @math ) for strip packing where rotations by 90 degrees are permitted and an algorithm for two-dimensional bin packing with an absolute worst-case ratio of 2, which is optimal provided @math .