Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More

Waldo Gálvez, Fabrizio Grandoni, Arindam Khan +2

In the \textsc{2-Dimensional Knapsack} problem (2DK) we are given a square knapsack and a collection of $n$ rectangular items with integer sizes and profits. Our goal is to find th…