License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.62
URN: urn:nbn:de:0030-drops-111831
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11183/
Jansen, Klaus ;
Rau, Malin
Closing the Gap for Pseudo-Polynomial Strip Packing
Abstract
Two-dimensional 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 pseudo-polynomial Strip Packing if we consider algorithms with pseudo-polynomial running time with respect to the width of the strip. It is known that there is no pseudo-polynomial 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 Pseudo-Polynomial Strip Packing}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {62:1--62:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11183},
URN = {urn:nbn:de:0030-drops-111831},
doi = {10.4230/LIPIcs.ESA.2019.62},
annote = {Keywords: Strip Packing, pseudo-polynomial, 90 degree rotation, Contiguous Moldable Task Scheduling}
}
|
Keywords: |
|
Strip Packing, pseudo-polynomial, 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 |
