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
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

URL of the conference:

http://cui.unige.ch/tcs/random-approx/2009/index.php

URL for downloading the paper:

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
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
01/13/2010 01:06:32 PM
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

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