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.
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 . This paper proposes a new approximation algorithm @math for packing rectangles into a strip with unit width and unbounded height so as to minimize the total height of the packing. It is shown that for any list @math of rectangles, @math , where @math is the strip height actually used by the algorithm @math when applied to @math and OPT @math is the minimum possible height within which the rectangles in @math can be packed.  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 problems of packing an arbitrary collection of rectangular pieces into an open-ended, rectangular bin so as to minimize the height achieved by any piece. This problem has numerous applications in operations research and studies of computer operation. We devise efficient approximation algorithms, study their limitations, and derive worst-case bounds on the performance of the packings they produce. 