Multidimensional Cube Packing |
| |
| Authors: | Yoshiharu Kohayakawa Flavio Keidi Miyazawa Prabhakar Raghavan Yoshiko Wakabayashi |
| |
| Affiliation: | (1) Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090 São Paulo SP, Brazil;(2) Instituto de Computação, Universidade Estadual de Campinas, Caixa Postal 6176, 13084-971 Campinas SP, Brazil;(3) Verity, Inc., 892 Ross Drive, Sunnyvale, CA 94089, USA |
| |
| Abstract: | We consider the d-dimensional cube packing problem (d-CPP): given a list L of d-dimensionalcubes and (an unlimited quantity of) d-dimensional unit-capacity cubes, called bins, find a packing of L intothe minimum number of bins. We present two approximation algorithms for d-CPP, for fixed d. The firstalgorithm has an asymptotic performance bound that can be made arbitrarily close to 2 – (1/2)d . The secondalgorithm is an improvement of the first and has an asymptotic performance bound that can be made arbitrarilyclose to 2 – (2/3)d . To our knowledge, these results improve the bounds known so far for d = 2 and d = 3, andare the first results with bounds that are not exponential in the dimension. |
| |
| Keywords: | Approximation algorithms Multidimensional bin packing Asymptotic performance |
| 本文献已被 SpringerLink 等数据库收录！ |
|
