Galvez, Waldo and Grandoni, Fabrizio and Khan, Arindam and Ramirez-Romero, Diego and Wiese, Andreas (2021) Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More. In: 37th International Symposium on Computational Geometry, SoCG 2021, June 7-11, 2021, Buffalo, NY, USA (Virtual Conference).
Full text not available from this repository.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 polynomialtime 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.
| Item Type: | Article in conference proceedings or Presentation at a conference (Paper) |
|---|---|
| Subjects: | Computer sciences > Computer science > Computational science foundations |
| Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull’intelligenza artificiale USI-SUPSI |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 17 Jul 2023 10:07 |
| Last Modified: | 17 Jul 2023 10:09 |
| URI: | http://repository.supsi.ch/id/eprint/14317 |
Actions (login required)
 |
View Item |