Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing

Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
EditorsMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772358
DOIs
StatePublished - 1 Jul 2022
Event49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, France
Duration: 4 Jul 20228 Jul 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume229
ISSN (Print)1868-8969

Conference

Conference49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
Country/TerritoryFrance
CityParis
Period4/07/228/07/22

Keywords

  • Approximation Algorithms
  • Computational Geometry
  • Guillotine Cuts
  • Rectangle Packing
  • Two-Dimensional Packing

Fingerprint

Dive into the research topics of 'Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing'. Together they form a unique fingerprint.

Cite this