TY - GEN
T1 - Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing
AU - Khan, Arindam
AU - Lonkar, Aditya
AU - Maiti, Arnab
AU - Sharma, Amatya
AU - Wiese, Andreas
N1 - Publisher Copyright:
© Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, and Andreas Wiese; licensed under Creative Commons License CC-BY 4.0
PY - 2022/7/1
Y1 - 2022/7/1
N2 - In the Strip Packing problem (SP), we are given a vertical half-strip [0, W] × [0, ∞) and a set of n axis-aligned rectangles of width at most W. The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied 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 edge-to-edge axis-parallel 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 NP-hard. Moreover, due to a reduction from the Partition problem, it is NP-hard to obtain a polynomial-time (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 pseudo-polynomial time (1 + ε)-approximation algorithm for GSP. This is surprising as it is NP-hard to obtain a (5/4 − ε)approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.
AB - In the Strip Packing problem (SP), we are given a vertical half-strip [0, W] × [0, ∞) and a set of n axis-aligned rectangles of width at most W. The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied 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 edge-to-edge axis-parallel 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 NP-hard. Moreover, due to a reduction from the Partition problem, it is NP-hard to obtain a polynomial-time (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 pseudo-polynomial time (1 + ε)-approximation algorithm for GSP. This is surprising as it is NP-hard to obtain a (5/4 − ε)approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.
KW - Approximation Algorithms
KW - Computational Geometry
KW - Guillotine Cuts
KW - Rectangle Packing
KW - Two-Dimensional Packing
UR - http://www.scopus.com/inward/record.url?scp=85133420177&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2022.80
DO - 10.4230/LIPIcs.ICALP.2022.80
M3 - Conference contribution
AN - SCOPUS:85133420177
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
A2 - Bojanczyk, Mikolaj
A2 - Merelli, Emanuela
A2 - Woodruff, David P.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
Y2 - 4 July 2022 through 8 July 2022
ER -