# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

##### External Resource

No external resources are shared

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Harren, R., & van Stee, R. (2009). Improved Absolute Approximation Ratios for Two-Dimensional
Packing Problems. In *Approximation, Randomization, and Combinatorial Optimization. Algorithms and
Techniques* (pp. 177-189). Berlin: Springer. doi:10.1007/978-3-642-03685-9_14.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1859-5

##### 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}$.