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.
There are many other related geometric packing problems. For example, in the problem we are given a collection of axis-parallel rectangles embedded in the plane, and we need to find a maximum cardinality weight subset of non-overlapping rectangles @cite_27 @cite_9 @cite_20 . Interesting connections between this problem and the problem were recently discovered @cite_39 @cite_14 @cite_13 . In the problem we wish to pack a maximum cardinality profit subset of the rectangles in a given square knapsack @cite_8 @cite_31 @cite_28 . added our FOCS paper. One can also consider a natural geometric version of bin packing, where the goal is to pack a given set of rectangles in the smallest possible number of square bins @cite_12 . We refer the readers to @cite_32 @cite_0 for surveys on geometric packing problems.
@cite_14 @cite_8 @cite_28 @cite_9 @cite_32 @cite_39 @cite_0 @cite_27 @cite_31 @cite_13 @cite_12 @cite_20
2770216739 2752916745 2962797157 1517042457
We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is (2 + ) [Jansen and Zhang, SODA 2004]. In this paper, we break the 2 approximation barrier, achieving a polynomial-time (17 9 + ) < 1.89 approximation, which improves to (558 325 + ) < 1.72 in the cardinality case. Essentially all prior work on 2DK approximation packs items inside a constant number of rectangular containers, where items inside each container are packed using a simple greedy strategy. We deviate for the first time from this setting: we show that there exists a large profit solution where items are packed inside a constant number of containers plus one L-shaped region at the boundary of the knapsack which contains items that are high and narrow and items that are wide and thin. As a second major and the main algorithmic contribution of this paper, we present a PTAS for this case. We believe that this will turn out to be useful in future work in geometric packing problems. We also consider the variant of the problem with rotations (2DKR), where items can be rotated by 90 degrees. Also, in this case, the best-known polynomial-time approximation factor (even for the cardinality case) is (2 + ) [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time (3 2 + )-approximation for 2DKR, which improves to (4 3 + ) in the cardinality case. In this paper we consider the Online Bin Packing Problem in three variants: Circles in Squares, Circles in Isosceles Right Triangles, and Spheres in Cubes. The two first ones receive an online sequence of circles (items) of different radii while the third one receive an online sequence of spheres (items) of different radii, and they want to pack the items into the minimum number of unit squares, isosceles right triangles of leg length one, and unit cubes, respectively. For Online Circle Packing in Squares, we improve the previous best-known competitive ratio for the bounded space version, when at most a constant number of bins can be open at any given time, from 2.439 to 2.3536. For Online Circle Packing in Isosceles Right Triangles and Online Sphere Packing in Cubes we show bounded space algorithms of asymptotic competitive ratios 2.5490 and 3.5316, respectively, as well as lower bounds of 2.1193 and 2.7707 on the competitive ratio of any online bounded space algorithm for these two problems. We also considered the online unbounded space variant of these three problems which admits a small reorganization of the items inside the bin after their packing, and we present algorithms of competitive ratios 2.3105, 2.5094, and 3.5146 for Circles in Squares, Circles in Isosceles Right Triangles, and Spheres in Cubes, respectively. We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is 2+&#x03B5; [Jansen and Zhang, SODA 2004]. In this paper we break the 2 approximation barrier, achieving a polynomialtime 17 9 + &#x03B5; Given a set Q of squares with positive profits, the square packing problem is to select and pack a subset of squares of maximum profit into a rectangular bin R. We present a polynomial time approximation scheme for this problem, that for any value Ɛ > 0 finds and packs a subset Q′ ⊆ Q of profit at least (1 - Ɛ)OPT, where OPT is the profit of an optimum solution. This settles the approximability of the problem and improves on the previously best approximation ratio of 5 4 +Ɛ achieved by Harren's algorithm.