Título: Otimização combinatória e algoritmos de aproximação

Palestrante: Carla Negri Lintzmayer (CMCC/UFABC)

Data e local: Quarta-feira, 15 de agosto de 2018, às 16h, Santo André, Bloco A, sala S-105-0.

Resumo: 

Problemas em Otimização Combinatória têm como objetivo encontrar a melhor solução dentro de um enorme mas finito conjunto de soluções possíveis. Eles surgem naturalmente de aplicações práticas (minimizar rotas de veículos, maximizar lucro, minimizar desperdício de material de produção, minimizar uso de recursos disponíveis, entre tantos outros) e, de modo geral, testar todos os elementos dentre as soluções possíveis na busca pela melhor mostra-se inviável na prática, mesmo para instâncias de tamanho moderado. Estratégias que tem tido sucesso para tratar estes problemas envolvem métodos em algoritmos de aproximação, heurísticas e programação inteira, por exemplo. Nessa palestra veremos um pouco mais sobre a área de pesquisa em otimização combinatória e, em particular, o uso de algoritmos de aproximação para tratar alguns desses problemas.