An Asymptotic Approximation Algorithm for 3D-Strip Packing
Klaus Jansen
Department of Computer Science
Universität Kiel
Wednesday, October 18, 2006
4:30 - 5:30 PM
Terman Engineering Center, Room 453
Abstract:
We present an asymptotic (2+ε)-approximation algorithm for
the 3D-strip packing problem, for any ε > 0. In the
3D-strip packing problem the input is a set L = {b_1, b2, ...,
b_n} of 3-dimensional boxes. Each box b_i has width, length, and
height at most 1. The problem is to pack the boxes into a
3-dimensional bin B of width 1, length 1 and minimum height, so
that the boxes do not overlap. We consider here only orthogonal
packings without rotations; this means that the boxes are packed so
that their faces are parallel to the faces of the bin, and rotations
are not allowed. This algorithm improves on the previously best
algorithm of Miyazawa and Wakabayashi which has asymptotic performance
ratio of 2.64. Our algorithm can be easily modified to a
(4+ε)-approximation algorithm for the 3D-bin packing
problem.
This is joint work with R. Solis-Oba (Univ. of Western Ontario).
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html