17 jun 2021
13:00 Defesa de Mestrado Integralmente a distância
Tema
In-line Packing of Circles
Aluno
Elisa Dell'Arriva
Orientador / Docente
Flávio Keidi Miyazawa
Breve resumo
Problemas de empacotamento formam uma diversa classe de problemas bastante úteis para modelagem de problemas práticos. Algumas delas são: corte de materiais, armazenamento e transporte de mercadorias, escalonamento de processos e alocação de propagandas.
Em particular, no problema de empacotamento de círculos em linha temos como entrada uma lista de círculos e desejamos empacotar todo círculo sobre uma linha horizontal de forma que cada círculo toque a linha por cima em exatamente um ponto, sem que ocorra sobreposição de itens. O objetivo é minimizar o \emph{span} do empacotamento, isto é, a distância entre o ponto mais à esquerda do empacotamento e o ponto mais à direita do empacotamento. Contudo, esse é um problema provado ser NP-difícil, o que significa que não existe algoritmo eficiente capaz de produzir uma solução ótima, a menos que P=NP. Sendo assim, um caminho natural é procurar por soluções com valores próximos do valor ótimo. Uma abordagem nessa direção é a de Algoritmos de Aproximação. Algoritmos de aproximação são algoritmos eficientes capazes de produzir uma solução com uma garantia em relação ao valor ótimo, para toda instância do problema. Neste trabalho, apresentamos alguns resultados encontrados na literatura e, além disso, investigamos alguns casos particulares do problema, propondo algumas soluções para tais casos.
Banca examinadora
Titulares:
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Eduardo Candido Xavier | IC/UNICAMP |
| Cristina Gomes Fernandes | IME/USP |
Suplentes:
| Christiane Neme Campos | IC/UNICAMP |
| Carlos Eduardo Ferreira | IME/USP |