\input zb-basic
\input zb-ioport
\iteman{io-port 00438799}
\itemau{Csirik, J\'anos; van Vliet, Andr\'e}
\itemti{An on-line algorithm for multidimensional bin packing.}
\itemso{Oper. Res. Lett. 13, No.3, 149-158 (1993).}
\itemab
Summary: We present an on-line algorithm for the $d$-dimensional bin 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 not a generalization of the 1-dimensional $\text{HARMONIC}\sb M$ algorithm of {\it C. C. Lee} and {\it D. T. Lee} [J. Assoc. Comput. Mach. 32, 562-572 (1985; Zbl 0629.68045)], we can use its worst case analysis to prove that our algorithm yields an asymptotic worst case ratio of $(1.691\dots)\sp d$. Further, we show that for uniformly distributed items the algorithm has an expected asymptotic efficiency of $\bigl (2({1\over 6} \pi\sp 2- 1)\bigr)\sp d$.
\itemrv{~}
\itemcc{}
\itemut{average case analysis; on-line algorithm; $d$-dimensional bin packing; worst case analysis}
\itemli{doi:10.1016/0167-6377(93)90004-Z}
\end