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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2008-12-186 |
| Date | 14 January 2010 |
| Creators | Li, Xiafeng |
| Contributors | Friesen, Donald |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation |
| Format | application/pdf |
Page generated in 0.0024 seconds