AN ONLINE ALGORITHM FOR MULTIDIMENSIONAL BIN PACKING

In this paper we present an on-line algorithm for the d-dimensional bi n packing problem. We use the idea of rounding up the size of an item to a size that can be packed efficiently. Although our algorithm is no t a generalization of the 1-dimensional HARMONIC(M) algorithm [6], we can use its worst case analysis to prove that our algorithm yields an asymptotic worst case ratio of (1.691...)d. Further, we show that for uniformly distributed items the algorithm has an expected asymptotic e fficiency of (2(1/6pi2 - 1))d.