Packing problems consist in placing a collection of objects inside recipients in an economical way. These problems can be of two types depending on the objective under consideration. In the first case, the objective is to minimize the number of recipients used to pack the objects. In the second case, the objects must be packed into only one recipient--whose dimensions are all bounded, except one--and the objective is to minimize the `size' of the packing, measured with respect to the unbounded dimension of the recipient.

In this thesis we consider packing problems where the objects and recipients
are 2- or 3-dimensional, and of `orthogonal shape'. Thus, the objects are
rectangles or rectangular boxes and the recipients are rectangular strips,
rectangular bins, rectangular boxes of unbounded height or rectangular boxes
of bounded dimensions (containers). Furthermore, all packings must be
orthogonal. We consider the following problems: the *strip packing problem*,
the *two-dimensional bin packing problem*, the *three dimensional packing
problem* and the *container packing problem*. These problems are
NP-hard, not approximable--in the absolute sense--within certain
constants. We present (polynomial) approximation algorithms for these problems and study
their asymptotic performance. We describe on-line and off-line algorithms for
the oriented case and for the case where orthogonal rotations are allowed.

For the strip packing problem, we present an algorithm with asymptotic performance bound at most 1.62 and an on-line algorithm with asymptotic performance bound 1.75. Both algorithms are for the case where orthogonal rotations are allowed. For the two-dimensional bin packing problem allowing orthogonal rotations, we present an algorithm with asymptotic performance bound at most 2.64 and an on-line algorithm with an asymptotic performance bound of 3.25. For the three-dimensional packing problem, we present an algorithm for the oriented case, with asymptotic performance bound at most 2.67. For the case where orthogonal rotations around the height axis are allowed, we present an algorithm whose asymptotic performance bound is at most 2.67 and another on-line algorithm with an asymptotic performance bound of 3.25. For the container packing problem where orthogonal rotations are allowed, we present an algorithm with asymptotic performance bound at most 4.89 and an on-line algorithm with asymptotic performance bound at most 6.25.

All the bounds above are either new or are improvements of the existing ones in the literature. Moreover, we present results relating the complexity of these problems in the oriented version with the version where orthogonal rotations are allowed. We also present several approximation algorithms for special cases of these problems: packing of squares, of cubes and of `small' objects. For these cases, we describe algorithms whose asymptotic performance bounds are better than those mentioned above.

**Keywords:** packing problems, approximation algorithms, asymptotic performance bound.

**Thesis supervisor:** YOSHIKO WAKABAYASHI.

Back to Flávio Keidi Miyazawa's Homepage

This document was generated using the **LaTeX**2`HTML`
translator Version 96.1-h (September 30, 1996) Copyright © 1993, 1994,
1995, 1996, Nikos
Drakos, Computer Based Learning Unit, University of Leeds.