Abstract: Bin packing is a well-known problem in optimization theory with many variants and applications in practice. An input to the problem is a multi-set of items with different sizes in the range (0,1], and the target is to pack them into the minimum number of bins of uniform capacity.

There are many ways to extend the well-known classic bin packing problem to two dimensions. Packing square-items into square-bins, called the square packing problem, is perhaps one of the most straightforward extensions. In this problem, the goal is to place a multiset of square items of various side-lengths of at most one into a minimum number of square bins of uniform side-length one such that two square-items placed in the same bin do not overlap (but they possibly touch each other). We refer to the number of bins used by an algorithm as the cost of the algorithm. Two-dimensional bin packing has many applications in practice. One application is cutting stuck, where bins represent the equal-size pieces of wood boards (stock), and items are demanded pieces of different sizes. An algorithm has to cut the stock to provide the pieces that match the requests, and its goal is to use the minimum number of wood boards, which is consistent with the objective of square packing.

Despite being studied previously, the existing models for the problem do not allow rotation of items. In this paper, we consider the square packing problem in the presence of rotation. As expected, we can show that the problem is NP-hard. We study the problem under a resource augmented setting where an approximation algorithm can use bins of size 1 + α, for some α > 0, while the algorithm’s packing is compared to an optimal packing into bins of size 1. Under this setting, we show that the problem admits an asymptotic polynomial time scheme (APTAS) whose solutions can be encoded in a poly-logarithmic number of bits.

See the full paper published on Springer: https://link.springer.com/chapter/10.1007/978-3-030-64843-5_36