Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
473938 | Computers & Operations Research | 2009 | 15 Pages |
Abstract
We present approximation algorithms for the three-dimensional strip packing problem, and the three-dimensional bin packing problem . We consider orthogonal packings where 90∘90∘ rotations are allowed. The algorithms we show for these problems have asymptotic performance bounds 2.64, and 4.89, respectively. These algorithms are for the more general case in which the bounded dimensions of the bin given in the input are not necessarily equal (that is, we consider bins for which the length, the width and the height are not necessarily equal). Moreover, we show that these problems—in the general version—are as hard to approximate as the corresponding oriented version.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
F.K. Miyazawa, Y. Wakabayashi,