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

Abstract:  In the 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 the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+eps<1.89 and there is a (3/2+eps)-approximation algorithm if we are allowed to rotate items by 90 degrees. In this talk, I will present a (4/3+eps)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n.

The previous best algorithm for 2DK partitions the knapsack into a constant number of rectangular regions plus one L-shaped region and packs items into those in a structured way. We generalize this approach by allowing up to a constant number of more general regions that can have the shape of an L, a U, a Z, a spiral, and more, and therefore obtain an improved approximation ratio. In particular, our results are achieved via an algorithm that computes the essentially optimal structured packing into these regions.

Joint work with Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero and Andreas Wiese.

Posted on May 10, 2021 in ACGO, Seminars