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):
Gudmundsson, Joachimdblp
Not MPII Editor(s):
Gudmundsson, Joachim
BibTeX cite key*:
HarrenvanStee2008
Title, Booktitle
Title*:
Packing Rectangles into 2 OPT Bins using Rotations
Harren,vanStee-SWAT2008.pdf (301.31 KB)
Booktitle*:
11th Scandinavian Workshop on Algorithm Theory
Event, URLs
Conference URL::
http://www.dmist.net/swat2008/
Downloading URL:
http://dx.doi.org/10.1007/978-3-540-69903-3_28
Event Address*:
Gothenburg, Sweden
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
2 July 2008
Event End Date:
4 July 2008
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
5124
Number:
Month:
July
Pages:
306-318
Year*:
2008
VG Wort Pages:
12
ISBN/ISSN:
978-3-540-69900-2
Sequence Number:
DOI:
10.1007/978-3-540-69903-3
Note, Abstract, ©
(LaTeX) Abstract:
We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles can be rotated by $90$ degrees and have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm for this problem with an absolute worst-case ratio of 2, which is optimal provided $\mathcal{P} \not= \mathcal{NP}$.
Keywords:
bin packing, rectangle packing, approximation algorithm, absolute worst-case ratio
Copyright Message:
Springer-Verlag Berlin Heidelberg 2008, published in:
Proc. of SWAT 2008, LNCS 5124, pp. 306--318, 2008
http://www.springer.de/comp/lncs/index.html
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{HarrenvanStee2008,
AUTHOR = {Harren, Rolf and van Stee, Rob},
 EDITOR = {Gudmundsson, Joachim},
 TITLE = {Packing Rectangles into 2 OPT Bins using Rotations},
 BOOKTITLE = {11th Scandinavian Workshop on Algorithm Theory},
 PUBLISHER = {Springer},
 YEAR = {2008},
 VOLUME = {5124},
 PAGES = {306--318},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Gothenburg, Sweden},
 MONTH = {July},
 ISBN = {978-3-540-69900-2},
 DOI = {10.1007/978-3-540-69903-3},
}

Entry last modified by Rob van Stee, 12/10/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)
Rolf Harren		Created
01/10/2009 05:48:23 AM
Revision
1.
0.


Editor
Rob van Stee
Rolf Harren


Edit Date
12-10-2010 15:36:15
10.01.2009 05:48:24


File Attachment Icon
Harren,vanStee-SWAT2008.pdf