| Article ID: | iaor20022338 |
| Country: | Brazil |
| Volume: | 19 |
| Issue: | 2 |
| Start Page Number: | 223 |
| End Page Number: | 237 |
| Publication Date: | Dec 1999 |
| Journal: | Pesquisa Operacional |
| Authors: | Wakabayashi Y., Ferreira C.E., Miyazawa F.K. |
| Keywords: | production |
We consider the problem of packing a list of squares into unit capacity squares. The objective of this problem is to minimize the number of unit capacity squares used in the packing. We consider a restricted version of this problem and exhibit a polynomial time algorithm to solve it. We use this algorithm in the design of an approximation algorithm for the original problem, and show that its asymptotic performance bound is 1.988. This bound compares favourably with the bound 2.125, known for an algorithm obtained by Chung, Garey & Johnson in 1982 for the more general problem, where the items to be packed are rectangles.