Journal Article
@Article
Artikel in Fachzeitschrift


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(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
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
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section