English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

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