Busca avançada
Ano de início
Entree

Problemas de otimização combinatória

Processo: 07/53286-8
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de agosto de 2007
Vigência (Término): 31 de julho de 2009
Área do 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   Programação linear

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)