MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Harren, Rolf
Jansen, Klaus
Prädel, Lars
van Stee, Rob		dblp
dblp
dblp
dblp
Not MPG Author(s):
Jansen, Klaus
Prädel, Lars
Editor(s):
Dehne, Frank
Iacono, John
Sack, Jörg-Rüdiger		dblp
dblp
dblp
Not MPII Editor(s):
Dehne, Frank
Iacono, John
Sack, Jörg-Rüdiger
BibTeX cite key*:
HaJaPS11
Title, Booktitle
Title*:
A (5/3 + ε)-Approximation for Strip Packing
strip53.pdf (489.41 KB)
Booktitle*:
Algorithms and Data Structures : 12th International Symposium, WADS 2011
Event, URLs
Conference URL::
http://wads.poly.edu/
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-22300-6_40
Event Address*:
New York, NY
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
12 December 2011
Event End Date:
12 December 2011
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
New York, NY
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6844
Number:
Month:
August
Pages:
475-487
Year*:
2011
VG Wort Pages:
13
ISBN/ISSN:
978-3-642-22299-3
Sequence Number:
DOI:
10.1007/978-3-642-22300-6_40
Note, Abstract, ©
(LaTeX) Abstract:
We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations into a strip of width $1$ and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of $5/3+\eps$ for any $\eps>0$. This result significantly narrows the gap between the best known upper bound and the lower bound of $3/2$; previously, the best upper bound was $1.9396$ due to Harren and van Stee.
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{HaJaPS11,
AUTHOR = {Harren, Rolf and Jansen, Klaus and Pr{\"a}del, Lars and van Stee, Rob},
 EDITOR = {Dehne, Frank and Iacono, John and Sack, J{\"o}rg-R{\"u}diger},
 TITLE = {A (5/3 + ε)-Approximation for Strip Packing},
 BOOKTITLE = {Algorithms and Data Structures : 12th International Symposium, WADS 2011},
 PUBLISHER = {Springer},
 YEAR = {2011},
 VOLUME = {6844},
 PAGES = {475--487},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {New York, NY},
 MONTH = {August},
 ISBN = {978-3-642-22299-3},
 DOI = {10.1007/978-3-642-22300-6_40},
}

Entry last modified by Anja Becker, 02/09/2012
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
12/12/2011 04:14:26 PM
Revision
1.
0.


Editor
Anja Becker
Rob van Stee


Edit Date
09.02.2012 14:14:20
12/12/2011 04:14:26 PM


File Attachment Icon
strip53.pdf