hal-00738614, version 1

## Approximation Algorithm for Multiple Strip Packing

Marin Bougeret () 1, Pierre-Francois Dutot () a23, Klaus Jansen 4, Christina Otte 4, Denis Trystram () b25

7th Workshop on Approximation and Online Algorithms (WAOA) 5893 (2009) 37-48

Résumé : 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.

• Domaine : Informatique/Algorithme et structure de données

• hal-00738614, version 1
• oai:hal.archives-ouvertes.fr:hal-00738614
• Contributeur :
• Soumis le : Jeudi 4 Octobre 2012, 16:27:37
• Dernière modification le : Mercredi 3 Avril 2013, 11:37:23