| dc.description.abstract | Bin packing is a very important and popular research area in the computer
science field. Past work showed many good and real-world packing algorithms. How-
ever, 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 dissertation, we extend 1D packing algorithms to hyperbox packing prob-
lems 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. In worst-
case analysis, we use the worst-case performance ratio as our metric and analyze the
relationship of the ratio of framework-based algorithms and that of the corresponding
1D algorithms. We also compare their worst-case performance against two baselines:
strip optimal algorithms and optimal algorithms. In average-case analysis, we use
expected waste as a metric, analyze the waste of optimal hyperbox packing algorithms,
and estimate the asymptotic forms of the waste for framework-based algorithms. | en |
