Improved Lower Bound for Online Strip Packing

Harren, Rolf; Kern, Walter

doi:10.1007/s00224-013-9494-8

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Improved Lower Bound for Online Strip Packing

MPS-Authors

/persons/resource/persons44587

Harren, Rolf
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., & Kern, W. (2015). Improved Lower Bound for Online Strip Packing. Theory of Computing Systems, 56(1), 41-72. doi:10.1007/s00224-013-9494-8.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-E518-4

Abstract

We study the online strip packing problem and derive an improved lower bound of rho a parts per thousand yen2.589aEuro broken vertical bar for the competitive ratio of this problem. The construction is based on modified "Brown-Baker-Katseff sequences" (Brown et al. in Acta Inform. 18:207-225, 1982) using only two types of rectangles. In addition, we present an online algorithm with competitive ratio for packing instances of this type.