Khan, Arindam ;
Lonkar, Aditya ;
Maiti, Arnab ;
Sharma, Amatya ;
Wiese, Andreas
Tight Approximation Algorithms for TwoDimensional Guillotine Strip Packing
Abstract
In the Strip Packing problem (SP), we are given a vertical halfstrip [0,W]×[0,∞) and a set of n axisaligned rectangles of width at most W. The goal is to find a nonoverlapping packing of all rectangles into the strip such that the height of the packing is minimized. A wellstudied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edgetoedge axisparallel cuts (guillotine cuts) that do not intersect any item of the solution. In this paper, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and also makespan minimization on identical machines, and thus it is already strongly NPhard. Moreover, due to a reduction from the Partition problem, it is NPhard to obtain a polynomialtime (3/2ε)approximation algorithm for GSP for any ε > 0 (exactly as Strip Packing). We provide a matching polynomial time (3/2+ε)approximation algorithm for GSP. Furthermore, we present a pseudopolynomial time (1+ε)approximation algorithm for GSP. This is surprising as it is NPhard to obtain a (5/4ε)approximation algorithm for (general) Strip Packing in pseudopolynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudopolynomial settings.
BibTeX  Entry
@InProceedings{khan_et_al:LIPIcs.ICALP.2022.80,
author = {Khan, Arindam and Lonkar, Aditya and Maiti, Arnab and Sharma, Amatya and Wiese, Andreas},
title = {{Tight Approximation Algorithms for TwoDimensional Guillotine Strip Packing}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {80:180:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16421},
URN = {urn:nbn:de:0030drops164215},
doi = {10.4230/LIPIcs.ICALP.2022.80},
annote = {Keywords: Approximation Algorithms, TwoDimensional Packing, Rectangle Packing, Guillotine Cuts, Computational Geometry}
}
28.06.2022
Keywords: 

Approximation Algorithms, TwoDimensional Packing, Rectangle Packing, Guillotine Cuts, Computational Geometry 
Seminar: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Issue date: 

2022 
Date of publication: 

28.06.2022 