Abstract:

We present an online algorithm for multidimensional bin packing
that is optimal among bounded space algorithms for any dimension d 1.
Its asymptotic performance ratio is (\Pi_{\infty})^d, where
\Pi_{\infty}\approx1.691 is the asymptotic performance ratio of
the one-dimensional algorithm Harmonic. A modified version of this 
algorithm for the case where all items are hypercubes is also shown 
to be optimal.  Its asymptotic performance ratio is sublinear in d.

Additionally, for the special case of packing squares in two-dimensional 
bins, we present a new unbounded space online algorithm with asymptotic
performance ratio of at most 2.271.
We also present an approximation algorithm for the offline problem with
approximation ratio of 16/11.
This improves upon all earlier approximation algorithms for this 
problem, including the algorithm from Caprara, Packing 2-dimensional bins in
harmony, Proc. 43rd FOCS, 2002.