# zbMATH — the first resource for mathematics

Packing rectangles in a strip. (English) Zbl 1034.68126
Summary: Rectangles with dimensions independently chosen from a uniform distribution on $$[0,1]$$ are packed on-line into a unit-width strip under a constraint like that of the Tetris$$^{\text{TM}}$$ game: rectangles arrive from the top and must be moved inside the strip to reach their place; once placed, they cannot be moved again. Cargo loading applications impose similar constraints. This paper assumes that rectangles must be moved without rotation. For $$n$$ rectangles, the resulting packing height is shown to have an asymptotic expected value of at least $$(0.31382733\ldots)n$$ under any on-line packing algorithm. An on-line algorithm is presented that achieves an asymptotic expected height of $$(0.36976421\ldots)n$$. This algorithm improves the bound achieved in Next Fit Level (NFL) packing, by compressing the items packed on two successive levels of an NFL packing via on-line movement admissible under the Tetris constraint.

##### MSC:
 68W40 Analysis of algorithms 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) 90B80 Discrete location and assignment
##### Keywords:
Tetris constraint
Full Text: