Palestra - Resolução Exata de Problemas de Otimização NP-difíceis em Geometria Computacional

Data: 
sexta-feira, 27 Outubro, 2017 - 14:30

Palestrantes: Prof. Cid de Souza (IC/UNICAMP)

Resumo:
São vários os problemas de Otimização NP-difíceis que são investigados por pesquisadores na área de
Geometria Computacional e para os quais nenhum algoritmo exato foi proposto e/ou testado experimentalmente.
O tratamento  comumente  dado  a  estes  problemas  se  concentra principalmente no desenvolvimento de algoritmos aproximados.
Ocorre que, na prática, tais algoritmos frequentemente produzem uma solução com custo bastante afastado
do ótimo. Nesta palestra será mostrado que instâncias de grande porte de alguns problemas geométricos podem
ser resolvidos à otimalidade ao se combinar, de forma engenhosa, técnicas de programação linear inteira
com o conhecimento de propriedades geométricas específicas do problema sendo tratado. Dentre os exemplos
bem-sucedidos de aplicação da metodologia será discutido o célebre Problema da Galeria de Artes.