Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

Harren, Rolf; van Stee, Rob

doi:10.1007/978-3-642-03685-9_14

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

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 (restricted access)

There are currently no full texts shared for your IP range.

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: https://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}$.