Yoshiko Wakabayashi
IME-USP
Sexta-feira, 19 de março de 2004, 14:00
Sala 267, Bloco A, IME-USP
Resumo:
Apresentaremos um APTAS (esquema de aproximação polinomial assintótico), isto é, um algoritmo polinomial assintótico $(1+\epsilon)$-aproximado, para o seguinte problema: dada uma coleção de cubos $d$-dimensionais, cada qual com lado menor que 1, encontrar um empacotamento desses cubos em um menor número possível de `bins' (cubos $d$-dimensionais unitários). Este resultado foi obtido recentemente (SODA 2004) por N. Bansal e J.R. Correa, e também por C. Kenyon e M. Sviridenko, independentemente.