The problem
In the square packing problem, the items are squares of different side lengths and the bins are unit squares. The goal is to place every item, without overlaps, into the smallest number of bins. It models cutting stock: a supplier cuts wooden boards into the pieces customers ask for and wants to use as few boards as possible.
The problem had been studied before, but the existing models didn't allow items to be rotated. In real cutting, a piece can be cut at any angle, so this work allows rotation by any degree.
What we showed
- The offline problem is NP-hard when rotation is allowed.
- Under a resource-augmented setting, where the algorithm may use bins slightly larger than the optimal solution's bins, we give an asymptotic polynomial-time approximation scheme (APTAS). Its solutions can be encoded in a poly-logarithmic number of bits.
My MSc thesis also covers the online version of the problem, with an online algorithm whose competitive ratio is at most 2.306, and a related problem of packing "tans" (half-square triangles) into unit squares, with an online algorithm whose competitive ratio is at most 1.897.