Multidimensional on-line bin packing: Algorithms and worst-case analysis

Don Coppersmith; Prabhakar Raghavan

doi:10.1016/0167-6377(89)90027-8

Operations Research Letters

Paper

01 Jan 1989

Multidimensional on-line bin packing: Algorithms and worst-case analysis

View publication

Abstract

We consider the problem of packing rectangles into bins which are unit squares. We give an on-line algorithm that uses at most 3.25 times the optimal number of bins. We also prove a result for the case when the items to be packed are squares and discuss extensions to higher dimensions. © 1989.

Conference paper