Abstract
Twodimensional packing problems are a fundamental class of optimization problems and Strip Packing is one of the most natural and famous among them. Indeed it can be defined in just one sentence: Given a set of rectangular axis parallel items and a strip with bounded width and infinite height, the objective is to find a packing of the items into the strip minimizing the packing height. We speak of pseudopolynomial Strip Packing if we consider algorithms with pseudopolynomial running time with respect to the width of the strip. It is known that there is no pseudopolynomial time algorithm for Strip Packing with a ratio better than 5/4 unless P = NP. The best algorithm so far has a ratio of 4/3 + epsilon. In this paper, we close the gap between inapproximability result and currently known algorithms by presenting an algorithm with approximation ratio 5/4 + epsilon. The algorithm relies on a new structural result which is the main accomplishment of this paper. It states that each optimal solution can be transformed with bounded loss in the objective such that it has one of a polynomial number of different forms thus making the problem tractable by standard techniques, i.e., dynamic programming. To show the conceptual strength of the approach, we extend our result to other problems as well, e.g., Strip Packing with 90 degree rotations and Contiguous Moldable Task Scheduling, and present algorithms with approximation ratio 5/4 + epsilon for these problems as well.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs:2019:11183,
author = {Klaus Jansen and Malin Rau},
title = {{Closing the Gap for PseudoPolynomial Strip Packing}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {62:162:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11183},
URN = {urn:nbn:de:0030drops111831},
doi = {10.4230/LIPIcs.ESA.2019.62},
annote = {Keywords: Strip Packing, pseudopolynomial, 90 degree rotation, Contiguous Moldable Task Scheduling}
}
Keywords: 

Strip Packing, pseudopolynomial, 90 degree rotation, Contiguous Moldable Task Scheduling 
Collection: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 