Packing Rectangles into 2 OPT Bins using Rotations

Harren, Rolf; van Stee, Rob

doi:10.1007/978-3-540-69903-3

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Packing Rectangles into 2 OPT Bins using Rotations

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. (2008). Packing Rectangles into 2 OPT Bins using Rotations. In J. Gudmundsson (Ed.), Algorithm Theory – SWAT 2008 (pp. 306-318). Berlin: Springer. doi:10.1007/978-3-540-69903-3.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1C97-E

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 can be rotated by $90$ degrees and have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm for this problem with an absolute worst-case ratio of 2, which is optimal provided $\mathcal{P} \not= \mathcal{NP}$.