Approximation Algorithm for Multiple Strip Packing

Marin Bougeret; Pierre-Francois Dutot; Klaus Jansen; Christina Otte; Denis Trystram

hal-00738614, version 1

Approximation Algorithm for Multiple Strip Packing

Marin Bougeret () ¹, Pierre-Francois Dutot ()^a^, 2, 3, Klaus Jansen ⁴, Christina Otte ⁴, Denis Trystram ()^b^, 2, 5

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.

a – Université Pierre Mendès-France - Grenoble II
b – Grenoble INP
1 : Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
CNRS : UMR5506 – Université Montpellier II - Sciences et techniques
2 : MOAIS (INRIA Grenoble Rhône-Alpes / LIG Laboratoire d'Informatique de Grenoble)
INRIA – Université Joseph Fourier - Grenoble I – Institut polytechnique de Grenoble (Grenoble INP) – Université Pierre-Mendès-France - Grenoble II – CNRS : UMR5217
3 : Université Pierre Mendès France (Grenoble 2 UPMF)
Université Pierre-Mendès-France - Grenoble II
4 : Department of Computer Science
CAU Kiel
5 : Institut Universitaire de France (IUF)
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique

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

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1007/978-3-642-12450-1_4

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="hal-00738614"><analytic>
<author><persName><forename>Marin</forename><surname>Bougeret</surname></persName>
<affiliation>
<orgName type="laboratory">LIRMM</orgName>
<orgName type="team">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5506</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<author><persName><forename>Pierre-Francois</forename><surname>Dutot</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LIG Laboratoire d'Informatique de Grenoble</orgName>
<orgName type="team">MOAIS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Institut polytechnique de Grenoble (Grenoble INP)</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
<orgName type="institution">CNRS : UMR5217</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">Grenoble 2 UPMF</orgName>
<orgName type="team">Université Pierre Mendès France</orgName>
<country>FR</country>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
</affiliation>
</author>
<author><persName><forename>Klaus</forename><surname>Jansen</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science</orgName>
<country>DE</country>
<orgName type="institution">CAU Kiel</orgName>
</affiliation>
</author>
<author><persName><forename>Christina</forename><surname>Otte</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science</orgName>
<country>DE</country>
<orgName type="institution">CAU Kiel</orgName>
</affiliation>
</author>
<author><persName><forename>Denis</forename><surname>Trystram</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LIG Laboratoire d'Informatique de Grenoble</orgName>
<orgName type="team">MOAIS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Institut polytechnique de Grenoble (Grenoble INP)</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
<orgName type="institution">CNRS : UMR5217</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">IUF</orgName>
<orgName type="team">Institut Universitaire de France</orgName>
<country>FR</country>
<orgName type="institution">Ministère de l'Enseignement Supérieur et de la Recherche Scientifique</orgName>
</affiliation>
</author>
<title type="main" level="a">Approximation Algorithm for Multiple Strip Packing</title></analytic><monogr><title level="m" type="main">Approximation and Online Algorithms</title><meeting>7th Workshop on Approximation and Online Algorithms (WAOA)</meeting><imprint><publisher>Springer</publisher><pubPlace><settlement>Copenhague</settlement><country>Danemark</country></pubPlace><biblScope type="publicationDate">2009-00-00</biblScope><biblScope type="vol">5893</biblScope><biblScope type="pp">37-48</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-642-12450-1_4</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00738614</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00738614/PDF/paper.pdf</idno></biblStruct>
</listBibl>
</listBibl>