ABSTRACT
This chapter presents the algorithm Next Fit Decreasing Height, which is a fundamental algorithm for two-dimensional packing problems. It discusses results on multidimensional packing problems, in order of increasing dimension and deals with strip packing and describes two-dimensional bin packing. It also discusses column packing, three- and more-dimensional bin packing. The chapter explores several variations on multidimensional packing and considers two- and three-dimensional strip packing, and bin packing in dimensions two and higher. It explains vector packing and several other variations and also considers only algorithmic aspects. The chapter analyses the nongeometric version of multidimensional bin packing. A multidimensional version of a dynamic bin packing model, which was introduced in reference 95 for the one-dimensional case, was studied by L. Epstein and M. Levy. Epstein and R. van Stee introduced a new technique for packing small multidimensional items online, enabling them to achieve the asymptotic approximation ratio of h∞d using only bounded space.
