Problemas de otimizacao combinatoria.

• Processo: 07/53286-8
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2007
• Data de Término da vigência: 31 de julho de 2009
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Orlando Lee
• Beneficiário: Guilherme Kunigami
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Otimização combinatória Teoria dos grafos Programação linear
• Palavra(s)-Chave do Pesquisador: Otimizacao Combinatoria | Programacao Linear | Teoria De Grafos

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)