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
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Approximation and Online Algorithms, 2010, Copenhagen, Denmark. 5893, pp.37-48, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-12450-1_4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00953421
Contributeur : Grégory Mounié <>
Soumis le : vendredi 28 février 2014 - 11:51:11
Dernière modification le : jeudi 11 janvier 2018 - 06:22:02

Identifiants

Collections

Citation

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. 5893, pp.37-48, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-12450-1_4〉. 〈hal-00953421〉

Partager

Métriques

Consultations de la notice

199