Um esquema de aproximação para um problema de empacotamento com cenários - Borges, Yulle; de Queiroz, Thiago; Lima, Vinícius; Miyazawa, Flavio; Pedrosa, Lehilton (Anais do Encontro de Teoria da Computação (ETC); 2019: Anais do IV Encontro de Teoria da Computação, 2019)
Investigamos um problema de empacotamento onde cada item possui um peso e está associado a um ou mais cenários e todos os recipientes têm uma capacidade fixa. Um empacotamento é uma atribuição de itens a recipientes de maneira que o peso total dos itens alocados a um recipiente para um mesmo cenário não ultrapasse a capacidade do recipiente. O objetivo do problema é encontrar um empacotamento de todos os itens em recipientes, de maneira a minimizar o número máximo de recipientes usados em qualquer cenário. Apre- sentamos um esquema de aproximação assintótico quando o número de cenários é limitado por uma constante.