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

Harren, Rolf; Jansen, Klaus; Prädel, Lars; van Stee, Rob

doi:10.1007/978-3-642-22300-6_40

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

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

MPS-Authors

/persons/resource/persons44587

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

/persons/resource/persons44695

Jansen, Klaus
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

There are no locators available

Fulltext (restricted access)

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

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/11858/00-001M-0000-0010-11D3-6

要旨

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.