MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Harren, Rolf
van Stee, Rob		dblp
dblp
Editor(s):
Dinur, Irit
Jansen, Klaus
Naor, Joseph
Rolim, José		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Dinur, Irit
Jansen, Klaus
Naor, Joseph
Rolim, José
BibTeX cite key*:
HarrenvanStee2009b
Title, Booktitle
Title*:
Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
Booktitle*:
Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009
Event, URLs
Conference URL::
http://cui.unige.ch/tcs/random-approx/2009/index.php
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-03685-9_14
Event Address*:
Berkeley, CA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
21 August 2009
Event End Date:
13 January 2010
Publisher
Name*:
Springer
URL:
http://www.springerlink.com/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
5687
Number:
Month:
August
Pages:
177-189
Year*:
2009
VG Wort Pages:
12
ISBN/ISSN:
978-3-642-03684-2
Sequence Number:
DOI:
10.1007/978-3-642-03685-9_14
Note, Abstract, ©
(LaTeX) Abstract:
We consider the two-dimensional bin packing and strip packing problem, where a list of rectangles has to be packed into a minimal number of rectangular bins or a strip of minimal height, respectively. All packings have to be non-overlapping and orthogonal, i.e., axis-parallel. Our algorithm for strip packing has an absolute approximation ratio of $1.9396$ and is the first algorithm to break the approximation ratio of 2 which was established more than a decade ago. Moreover, we present an algorithm for two-dimensional bin packing with an absolute worst-case ratio of 2, which is optimal provided $\mathcal{P} \not= \mathcal{NP}$.
Keywords:
two-dimensional bin packing, strip packing, rectangle packing, approximation algorithm, absolute worst-case ratio
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{HarrenvanStee2009b,
AUTHOR = {Harren, Rolf and van Stee, Rob},
 EDITOR = {Dinur, Irit and Jansen, Klaus and Naor, Joseph and Rolim, Jos{\'e}},
 TITLE = {Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems},
 BOOKTITLE = {Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009},
 PUBLISHER = {Springer},
 YEAR = {2009},
 VOLUME = {5687},
 PAGES = {177--189},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Berkeley, CA},
 MONTH = {August},
 ISBN = {978-3-642-03684-2},
 DOI = {10.1007/978-3-642-03685-9_14},
}

Entry last modified by Anja Becker, 03/08/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
01/13/2010 13:06:32
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Anja Becker
Rolf Harren

Edit Dates
08.03.2010 11:35:42
08.03.2010 11:25:08
13.01.2010 13:06:32