Towards a Key Problem in Information Technology: a Generic Approach to Multi-dimensional Bin Packing

Bin packing is a very important and popular research area in the computer science field. Practical solutions to this abstracted problem will significantly help computer engineers to build information technology systems. Past work showed many good and real-world packing algorithms. However, due to the complexity of the problem in multiple-dimensional bin packing, also called hyperbox packing, we need more practical packing algorithms for its real-world applications. In this book, we extend 1D packing algorithms to hyperbox packing problems via a general framework that takes two inputs of a 1D packing algorithm and an instance of hyperbox packing problem and outputs a hyperbox packing algorithm. The extension framework significantly enriches the family of hyperbox-packing algorithms, generates many framework-based algorithms, and simultaneously calls for the analysis for those algorithms. We also analyze the performance of a couple of framework-based algorithms from two perspectives of worst-case performance and average-case performance.