On discrete hyperbox packing /
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis eBook |
| Language: | English |
| Published: |
[College Station, Tex.] :
[Texas A&M University],
[2010]
|
| Subjects: | |
| Online Access: | Link to OAK Trust copy |
| 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. |
|---|---|
| Item Description: | "Major Subject: Computer Science" Title from author supplied metadata (automated record created 2010-03-12 12:08:51). Electronic resource. |
| Physical Description: | 1 online resource. |
| Bibliography: | Includes bibliographical references. |