Approximation Algorithm for Multiple Strip Packing

Marin Bougeret 1 Pierre-Francois Dutot 2 Klaus Jansen 3 Christina Otte 3 Denis Trystram 2, 4
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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
CAU - Christian-Albrechts-Universität [Kiel], Department of Computer Science
Abstract : In 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,\ldots,r_n$, with heights and widths $\le 1$, the goal is to find a non-overlapping orthogonal packing without rotations into $k\in\mathbb{N}$ strips $[0,1]\times[0,\infty)$, minimizing the maximum of the heights. We present an approximation algorithm with absolute ratio $2$, which is the best possible, unless ${\cal P}={\cal NP}$, and an improvement of the previous best result with ratio $2+\EPS$. Furthermore we present simple shelf-based algorithms with short running-time and an AFPTAS for MSP. Since MSP is strongly ${\cal NP}$-hard, an FPTAS is ruled out and an AFPTAS is also the best possible result in the sense of approximation theory.
Document type :
Conference papers
WAOA'2009: 7th Workshop on Approximation and Online Algorithms, Sep 2009, Copenhague, Denmark. Springer, 5893, pp.37-48, 2009, LNCS. <10.1007/978-3-642-12450-1_4>


https://hal.archives-ouvertes.fr/hal-00738614
Contributor : Marin Bougeret <>
Submitted on : Thursday, October 4, 2012 - 4:27:37 PM
Last modification on : Tuesday, July 21, 2015 - 9:57:41 AM

File

paper.pdf
fileSource_public_author

Identifiers

Collections

Citation

Marin Bougeret, Pierre-Francois Dutot, Klaus Jansen, Christina Otte, Denis Trystram. Approximation Algorithm for Multiple Strip Packing. WAOA'2009: 7th Workshop on Approximation and Online Algorithms, Sep 2009, Copenhague, Denmark. Springer, 5893, pp.37-48, 2009, LNCS. <10.1007/978-3-642-12450-1_4>. <hal-00738614>

Export

Share

Metrics

Consultation de
la notice

86

Téléchargement du document

48