TY - GEN
T1 - Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
AU - Gálvez, Waldo
AU - Grandoni, Fabrizio
AU - Khan, Arindam
AU - Ramírez-Romero, Diego
AU - Wiese, Andreas
N1 - Conference held: June 7-11, 2021, Buffalo, NY, USA (Virtual Conference).
PY - 2021
Y1 - 2021
N2 - 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+ε < 1.89 and there is a (3/2+ε)-approximation algorithm if we are allowed to rotate items by 90 degrees [Gálvez et al., FOCS 2017]. In this paper, we give (4/3+ε)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n.
Gálvez et al.’s 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, we present an algorithm that computes the essentially optimal structured packing into these regions.
AB - 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+ε < 1.89 and there is a (3/2+ε)-approximation algorithm if we are allowed to rotate items by 90 degrees [Gálvez et al., FOCS 2017]. In this paper, we give (4/3+ε)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n.
Gálvez et al.’s 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, we present an algorithm that computes the essentially optimal structured packing into these regions.
U2 - 10.4230/LIPIcs.SoCG.2021.39
DO - 10.4230/LIPIcs.SoCG.2021.39
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 17
BT - 37th International Symposium on Computational Geometry (SoCG 2021)
A2 - Buchin, Kevin
A2 - Verdière, Éric Colin de
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ER -