Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:

http://wads.poly.edu/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
strip53.pdf