
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 9704
ABSTRACT
Rectangles with dimensions independently chosen from a uniform
distribution on [ 0 , 1 ] are packed online 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
online packing algorithm. An online 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 online movement admissible under the Tetrislike 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 079742070