Approximation Algorithm for Multiple Strip Packing - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Approximation Algorithm for Multiple Strip Packing

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.
Fichier principal
Vignette du fichier
paper.pdf (156.36 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00738614 , version 1 (04-10-2012)

Identifiants

Citer

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. pp.37-48, ⟨10.1007/978-3-642-12450-1_4⟩. ⟨hal-00738614⟩
552 Consultations
398 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More