Algoritmos para Problemas de Empacotamento - Xavier, E. C.; Miyazawa, F. K. (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2007: Anais do XX Concurso de Teses e Dissertações, 2007)
Estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumimos a hipótese de que P ≠ NP e deste modo não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Desta forma, apresentamos algoritmos aproximados (algoritmos eficientes e que geram soluções com garantia de qualidade) para problemas de empacotamento com aplicações práticas. Alguns dos fatores de aproximação apresentados são os melhores conhecidos para os problemas correspondentes. Também apresentamos heurísticas baseadas em programação linear usando a técnica de geração de colunas para problemas de empacotamento bidimensional. Os resultados computacionais sugerem que tais heurísticas obtêm soluções de muito boa qualidade para instâncias reais.