de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### A (5/3 + ε)-Approximation for Strip Packing

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44587

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44695

Jansen,  Klaus
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45543

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

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Harren, R., Jansen, K., Prädel, L., & van Stee, R. (2011). A (5/3 + ε)-Approximation for Strip Packing. In F. Dehne, J. Iacono, & J.-R. Sack (Eds.), Algorithms and Data Structures (pp. 475-487). Berlin: Springer. doi:10.1007/978-3-642-22300-6_40.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-11D3-6
##### Abstract
We study strip packing, which is one of the most classical two-dimensional packing problems: given a collection of rectangles, the problem is to find a feasible orthogonal packing without rotations into a strip of width \$1\$ and minimum height. In this paper we present an approximation algorithm for the strip packing problem with absolute approximation ratio of \$5/3+\eps\$ for any \$\eps>0\$. This result significantly narrows the gap between the best known upper bound and the lower bound of \$3/2\$; previously, the best upper bound was \$1.9396\$ due to Harren and van Stee.