MPI-INF D1 Publications: Journal Article: Absolute Approximation Ratios for Packing Rectangles into Bins

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor(s)

Author(s):

Harren, Rolf
van Stee, Rob

dblp
dblp

BibTeX cite key*:

HarSte12

Title

Title*:

Absolute Approximation Ratios for Packing Rectangles into Bins

Journal

Journal Title*:	Journal of Scheduling	Journal's URL:	http://www.springer.com/business+%26+management/operations+research/journal/10951
Download URL for the article:	http://dx.doi.org/10.1007/s10951-009-0110-3	Language:	English

Publisher

Publisher's Name:	Springer	Publisher's URL:	http://www.springer-ny.com/
Publisher's Address:	New York, NY	ISSN:	1094-6136

Vol, No, pp, Date

Volume*:	15	Number:	1
Publishing Date:	February 2012
Pages*:	63-75	Number of VG Pages:	13
Page Start:	63	Page End:	75
Sequence Number:		DOI:	10.1007/s10951-009-0110-3

Note, Abstract, ©

Note:
(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 have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm with an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided P != NP. For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm Hybrid First Fit which was introduced by Chung, Gary \& Johnson [1982] and whose running time is slightly better than the running time of Zhang's previously known 3-approximation algorithm [2005].
URL for the Abstract:
Categories, Keywords:
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
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:

@ARTICLE{HarSte12,
AUTHOR = {Harren, Rolf and van Stee, Rob},
TITLE = {Absolute Approximation Ratios for Packing Rectangles into Bins},
JOURNAL = {Journal of Scheduling},
PUBLISHER = {Springer},
YEAR = {2012},
NUMBER = {1},
VOLUME = {15},
PAGES = {63--75},
ADDRESS = {New York, NY},
MONTH = {February},
ISBN = {1094-6136},
DOI = {10.1007/s10951-009-0110-3},
}

Entry last modified by Anja Becker, 02/04/2013

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 02/20/2009 12:49:26 PM
Revisions 10. 9. 8. 7. 6.	Editor(s) Anja Becker Rob van Stee Rob van Stee Rob van Stee Rob van Stee	Edit Dates 04.02.2013 13:51:06 11/23/2012 12:27:52 PM 11/14/2012 11:30:31 AM 12/12/2011 04:04:42 PM 03/03/2011 06:00:26 PM

Attachment Section