Khan, Arindam ;
Maiti, Arnab ;
Sharma, Amatya ;
Wiese, Andreas
On Guillotine Separable Packings for the TwoDimensional Geometric Knapsack Problem
Abstract
In twodimensional geometric knapsack problem, we are given a set of n axisaligned rectangular items and an axisaligned squareshaped knapsack. Each item has integral width, integral height and an associated integral profit. The goal is to find a (nonoverlapping axisaligned) packing of a maximum profit subset of rectangles into the knapsack. A wellstudied and frequently used constraint in practice is to allow only packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edgetoedge axisparallel cuts that do not intersect any item of the solution. In this paper we study approximation algorithms for the geometric knapsack problem under guillotine cut constraints. We present polynomial time (1+ε)approximation algorithms for the cases with and without allowing rotations by 90 degrees, assuming that all input numeric data are polynomially bounded in n. In comparison, the bestknown approximation factor for this setting is 3+ε [JansenZhang, SODA 2004], even in the cardinality case where all items have the same profit.
Our main technical contribution is a structural lemma which shows that any guillotine packing can be converted into another structured guillotine packing with almost the same profit. In this packing, each item is completely contained in one of a constant number of boxes and 𝖫shaped regions, inside which the items are placed by a simple greedy routine. In particular, we provide a clean sufficient condition when such a packing obeys the guillotine cut constraints which might be useful for other settings where these constraints are imposed.
BibTeX  Entry
@InProceedings{khan_et_al:LIPIcs.SoCG.2021.48,
author = {Khan, Arindam and Maiti, Arnab and Sharma, Amatya and Wiese, Andreas},
title = {{On Guillotine Separable Packings for the TwoDimensional Geometric Knapsack Problem}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {48:148:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771849},
ISSN = {18688969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13847},
URN = {urn:nbn:de:0030drops138474},
doi = {10.4230/LIPIcs.SoCG.2021.48},
annote = {Keywords: Approximation Algorithms, Multidimensional Knapsack, Guillotine Cuts, Geometric Packing, Rectangle Packing}
}
02.06.2021
Keywords: 

Approximation Algorithms, Multidimensional Knapsack, Guillotine Cuts, Geometric Packing, Rectangle Packing 
Seminar: 

37th International Symposium on Computational Geometry (SoCG 2021)

Issue date: 

2021 
Date of publication: 

02.06.2021 