Two- and three-dimensional parametric packing |
| |
Authors: | F.K. Miyazawa Y. Wakabayashi |
| |
Affiliation: | 1. Instituto de Computação, Universidade Estadual de Campinas, Caixa Postal 6176, 13084–971, Campinas–SP, Brazil;2. Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão, 1010, 05508–090, São Paulo, SP, Brazil |
| |
Abstract: | We present approximation algorithms for the two- and three-dimensional bin packing problems and the three-dimensional strip packing problem. We consider the special case of these problems in which a parameter m (a positive integer) is given, indicating that each of the dimensions of the items to be packed is at most 1/m of the corresponding dimension of the recipient. We analyze the asymptotic performance of these algorithms and exhibit bounds that, to our knowledge, are the best known for this special case. |
| |
Keywords: | Approximation algorithms Asymptotic performance Packing |
本文献已被 ScienceDirect 等数据库收录! |
|