Skip to Main content Skip to Navigation
New interface
Conference papers

Approximation Algorithms for Multiple Strip Packing

Marin Bougeret 1, 2, * Pierre-François Dutot 2 Klaus Jansen 3 Christina Otte 3 Denis Trystram 1, 2 
* Corresponding author
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 Theory of Parallelism
Department of Computer Science
Abstract : n this paper we study the Multiple Strip Packing (MSP) problem, a generalization of the well-known Strip Packing problem. For a given set of rectangles, r 1,...,r n , with heights and widths ≤ 1, the goal is to find a non-overlapping orthogonal packing without rotations into k ∈ ℕ strips [0,1]×[0, ∞ ), minimizing the maximum of the heights. We present an approximation algorithm with absolute ratio 2, which is the best possible, unless P=NP , and an improvement of the previous best result with ratio 2 + ε. Furthermore we present simple shelf-based algorithms with short running-time and an AFPTAS for MSP. Since MSP is strongly NP -hard, an FPTAS is ruled out and an AFPTAS is also the best possible result in the sense of approximation theory.
Complete list of metadata
Contributor : Grégory Mounié Connect in order to contact the contributor
Submitted on : Friday, February 28, 2014 - 11:51:11 AM
Last modification on : Wednesday, July 6, 2022 - 4:17:17 AM

Links full text



Marin Bougeret, Pierre-François Dutot, Klaus Jansen, Christina Otte, Denis Trystram. Approximation Algorithms for Multiple Strip Packing. Approximation and Online Algorithms, 2010, Copenhagen, Denmark. pp.37-48, ⟨10.1007/978-3-642-12450-1_4⟩. ⟨hal-00953421⟩



Record views