English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### MPS-Authors
/persons/resource/persons44587

Harren,  Rolf
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45543

van Stee,  Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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