Packing Rectangles in a Strip

E.G. Coffman, Jr.
Bell Laboratories/Lucent Technologies?

Peter J. Downey
University of Arizona

Peter Winkler
Bell Laboratories/Lucent Technologies?

TR 97-04

ABSTRACT

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? 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 ... ) n under any on-line packing algorithm. An on-line algorithm is presented that achieves an asymptotic expected height of ( 0. 36976421 ... ) 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-like constraint.

April 8, 1997

Department of Computer Science

The University of Arizona

Tucson, Arizona 85721

_ ______________
?Bell Laboratories, Lucent Technologies, 600 Mountain Ave, Murray Hill NJ 07974-2070