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:








Author, Editor

Author(s):

Harren, Rolf
van Stee, Rob

dblp
dblp



Editor(s):

Gudmundsson, Joachim

dblp

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

URL of the conference:

http://www.dmist.net/swat2008/

URL for downloading the paper:

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


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

View attachments here:


File Attachment Icon
Harren,vanStee-SWAT2008.pdf