# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Absolute Approximation Ratios for Packing Rectangles into Bins

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Harren, R., & van Stee, R. (2012). Absolute Approximation Ratios for Packing Rectangles
into Bins.* Journal of Scheduling,* *15*(1), 63-75. doi:10.1007/s10951-009-0110-3.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-BCEA-7

##### 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].