Data: 12/11/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Algoritmos de aproximação para problemas de empacotamento
Palestrante: Flávio Miyazawa (Unicamp)


Resumo: Problemas de empacotamento consistem em colocar, de uma forma econômica, uma coleção de objetos dentro de recipientes. Problemas clássicos desse tipo são os de empacotamento de objetos unidimensionais (p.ex. barras), bidimensionais (p.ex. retângulos e discos) e tridimensionais (p.ex. caixas e contêineres) em recipientes de mesma natureza, procurando otimizar o uso dos recipientes. Existem diversas variantes e objetivos específicos e, em geral, recaem em problemas NP-difíceis. Estes problemas são de grande importância e ocorrem em inúmeras aplicações, tendo sido investigadas sob várias abordagens. Nesta apresentação, nos concentraremos na abordagem de algoritmos de aproximação, que são algoritmos de complexidade de tempo polinomial que, para cada entrada, produzem uma solução com garantia de desempenho em relação a uma solução ótima. Apresentaremos alguns problemas de empacotamento e comentaremos alguns resultados e ideias envolvidas no desenvolvimento de algoritmos de aproximação.