05 abr 2023
14:00 Defesa de Mestrado Auditório do IC3
Tema
Algoritmos de Aproximação para o Problema do Empacotamento de Soma Mínima Bidimensional
Aluno
Rachel Vanucchi Saraiva
Orientador / Docente
Rafael Crivellari Saliba Schouery
Breve resumo
O trabalho trata da variante soma mínima do problema do empacotamento para itens quadrados, em que uma lista de itens quadrados deve ser empacotada em recipientes quadrados de dimensões 1 x 1, o custo de empacotar cada item é igual ao índice do recipiente em que é empacotado, e o objetivo é minimizar o custo total de empacotar todos os itens. O problema tem aplicações na minimização do tempo médio de operações logísticas como corte e entrega de produtos. Nesse trabalho provamos que algoritmos clássicos para empacotamento bidimensional que ordenam itens em ordem não-crescente de tamanho, como Hybrid First Fit, são arbitrariamente ruins para essa variante do problema. Apresentamos então uma 5/2-aproximação e um PTAS para a variante.
Banca examinadora
Titulares:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Yoshiko Wakabayashi | IME/USP |
Suplentes:
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Carla Negri Lintzmayer | CMCC/UFABC |