Gálvez, Waldo ;
Grandoni, Fabrizio ;
Ameli, Afrouz Jabal ;
Jansen, Klaus ;
Khan, Arindam ;
Rau, Malin
A Tight (3/2+ε) Approximation for Skewed Strip Packing
Abstract
In the Strip Packing problem, we are given a vertical halfstrip [0,W]× [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axisaligned (nonoverlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical wellstudied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption in smart grids among others. It is NPhard to approximate this problem within a factor (3/2ε) for any constant ε > 0 by a simple reduction from the Partition problem. The current best approximation factor for Strip Packing is (5/3+ε) by Harren et al. [Computational Geometry '14], and it is achieved with a fairly complex algorithm and analysis.
It seems plausible that Strip Packing admits a (3/2+ε)approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0, we call large the rectangles with width at least δ W and height at least δ OPT, and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, it is NPhard to approximate within a factor (3/2ε) and we provide an (almost) tight (3/2+ε)approximation algorithm.
BibTeX  Entry
@InProceedings{glvez_et_al:LIPIcs:2020:12647,
author = {Waldo G{\'a}lvez and Fabrizio Grandoni and Afrouz Jabal Ameli and Klaus Jansen and Arindam Khan and Malin Rau},
title = {{A Tight (3/2+ε) Approximation for Skewed Strip Packing}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {44:144:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12647},
URN = {urn:nbn:de:0030drops126478},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.44},
annote = {Keywords: strip packing, approximation algorithm}
}
11.08.2020
Keywords: 

strip packing, approximation algorithm 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 