Empacotamento de Cubos d-Dimensionais 

                      Flávio K. Miyazawa

            Sexta-feira, 5 de abril, sala 96, 18:00hs 

 Dado uma lista L de cubos d-dimensionais e (uma quantidade
 ilimitada) de cubos d-dimensionais unitários, chamados 'bins',
 encontrar um empacotamento de L no menor número de bins
 possível. Para o caso em que d=1, este problema é o problema de
 empacotamento unidimensional, (bin packing problem). Apresentaremos
 dois algoritmos de aproximação para este problema quando a dimensão
 é fixa. O primeiro tem fator de aproximação assintótico que pode ser
 tomado tão próximo de 2-(1/2)^d quanto se queira e o segundo, uma
 melhoria do primeiro, tem um fator de aproximação assintótico que
 pode ser tomado tão próximo de 2-(2/3)^d quanto se queira. São os
 primeiros resultados deste problema com fatores que não são
 exponenciais na dimensão.
 Trabalho em conjunto com Y. Kohayakawa, P. Raghavan e Y. Wakabayashi.