Problemas de otimizacao combinatoria.

Resumo

O objetivo deste projeto de iniciação científica é estudar várias técnicas e idéias usadas em Otimização Combinatória. Estudaremos programação linear e a teoria da dualidade e veremos como vários conceitos e métodos típicos dessas áreas podem ser usados no projeto de algoritmos eficientes para resolver problemas de otimização em grafos e de fluxos em redes. Paralelamente, pretendemos estudar a teoria (combinatória poliédrica) que está estreitamente relacionada com tais problemas. Outra vertente que pretendemos explorar é o estudo de algumas das técnicas usadas para o tratamento de problemas NP-difíceis: programação linear inteira, algoritmos de aproximação e busca local. Espera-se que ao final do projeto o aluno tenha adquirido familiaridade com várias técnicas e idéias típicas em Otimização Combinatória, visando um futuro estudo de outros tópicos mais avançados. (AU)