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.
The first approximation algorithm for the rectangle strip packing problem was proposed by Baker @cite_25 . They presented the so called BL (Bottom-Leftmost) algorithm, and showed that it has approximation ratio @math . For the special case when all items are squares, the approximation ratio of BL algorithm is at most @math . Coffman @cite_17 presented three algorithms, denoted by NFDH (Next Fit Decreasing Height), FFDH (First Fit Decreasing Height), and SF (Split Fit), with asymptotic approximation ratios of @math , @math , and @math , respectively. They also showed that, when the items are squares, FFDH has an asymptotic approximation ratio of @math , and, when all items have width at most @math , the algorithms FFDH and SFFDH have asymptotic approximation ratios of @math and @math , respectively. The best known ratio for the problem was obtained by Kenyon and R 'emila @cite_19 , who presented an asymptotic approximation scheme. Considering non-asymptotic approximation algorithms, Sleator @cite_24 presented a ratio @math . This result was improved to @math independently by Schiermeyer @cite_27 and Steinberg @cite_7 , then to @math by Harren and van Stee @cite_26 , and finally to @math by Harren @cite_10 .
@cite_26 @cite_7 @cite_24 @cite_19 @cite_27 @cite_10 @cite_25 @cite_17
2013696768 2060963575 2098666887 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 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. 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 .