Improved pseudo-polynomial-time approximation for strip packing

DOI10.4230/LIPICS.FSTTCS.2016.9MaRDI QIDQ4636556zbMATH OpenOpenAlexFDO

Authors Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, Arindam Khan

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1801.07541

zbMATH Keywords

approximation algorithmscutting-stock problemrectangle packingstrip packing

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in the two-dimensional plane and the goal is to pack them in a vertical strip of a fixed width such that the height of the obtained packing is minimized. The packing must be non-overlapping and the rectangles cannot be rotated. A reduction from the partition problem shows that no approximation better than 3/2 is possible for strip packing in polynomial time (assuming P$eq$NP). Nadiradze and Wiese [SODA16] overcame this barrier by presenting a $(frac75+epsilon)$-approximation algorithm in pseudo-polynomial-time (PPT). As the problem is strongly NP-hard, it does not admit an exact PPT algorithm. In this paper, we make further progress on the PPT approximability of strip packing, by presenting a $(frac43+epsilon)$-approximation algorithm. Our result is based on a non-trivial repacking of some rectangles in the emph{empty space} left by the construction by Nadiradze and Wiese, and in some sense pushes their approach to its limit. Our PPT algorithm can be adapted to the case where we are allowed to rotate the rectangles by $90^{c}irc$, achieving the same approximation factor and breaking the polynomial-time approximation barrier of 3/2 for the case with rotations as well.

Recommendations

• On approximating strip packing with a better ratio than 3/2
• A (5/3 + )-approximation for strip packing
• A (5/3+)-approximation for strip packing

Cited in

(15)

• Approximation and online algorithms for multidimensional bin packing: a survey
• Approximate strip packing: revisited
• On approximating strip packing with a better ratio than 3/2
• Hardness of approximation for strip packing
• Closing the Gap for Pseudo-Polynomial Strip Packing
• A (5/3 + )-approximation for strip packing
• A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing
• Peak demand minimization via sliced strip packing
• A Tight (3/2+ε) Approximation for Skewed Strip Packing.
• Approximation Algorithms for Demand Strip Packing
• An improved approximation algorithm for scheduling monotonic moldable tasks
• Tight approximation algorithms for 2D guillotine strip packing
• Approximation algorithms for round-UFP and round-SAP
• Improved approximation algorithms for 2-dimensional knapsack: packing into multiple l-shapes, spirals, and more
• On guillotine separable packings for the two-dimensional geometric knapsack problem

This page was built for publication: Improved pseudo-polynomial-time approximation for strip packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636556)