An on-line algorithm for multidimensional bin packing

In this paper the authors present an on-line algorithm for the d-dimensional bin packing problem. They use the idea of rounding up the size of an item to a size that can be packed efficiently. Although the present algorithm is not a generalization of the 1-dimensional HARMONICM algorithm, the authors can use its worst case analysis to prove that the algorithm yields an asymptotic worst case ratio of . Further, they show that for uniformly distributed items the algorithm has an expected asymptotic efficiency of .