Algoritmos de aproximação para empacotamento de hipercubos

Resumo:

O Problema do Empacotamento de cubos d-dimensionais (PEC-d) consiste no seguinte: dada uma lista L de cubos d-dimensionais e (uma quantidade ilimitada de) cubos d-dimensionais de capacidade unitária, chamados 'bins', encontrar um empacotamento de L em um número mínimo de bins. Apresentamos dois 'esquemas de aproximação' para o PEC-d. O primeiro tem razão de desempenho assintótico 2 - (1/2)^d + \epsilon e o segundo, que resulta de um melhoramento do primeiro, tem razão de desempenho assintótico 2 - (2/3)^d+ \epsilon. Esses resultados melhoram as razões conhecidas para d=2 e d=3, e são novas para os casos d >= 4. sendo os primeiros com razões que não são exponenciais na dimensão d.