| Processo: | 19/13311-0 |
| Linha de fomento: | Bolsas no Brasil - Iniciação Científica |
| Vigência (Início): | 01 de setembro de 2019 |
| Vigência (Término): | 31 de agosto de 2020 |
| Área do conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Pesquisador responsável: | Carla Negri Lintzmayer |
| Beneficiário: | Wesley Lima de Araujo |
| Instituição-sede: | Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brasil |
| Assunto(s): | Algoritmos de aproximação Otimização combinatória |
Resumo Em um problema de otimização combinatória o objetivo é encontrar uma solução de custo mínimo ou máximo dentre todas as soluções possíveis. Em geral, tais problemas são NP-difíceis, de modo que não se têm esperança de conseguir algoritmos que os resolvam em tempo polinomial. Um algoritmo de aproximação é um algoritmo que executa em tempo polinomial e retorna uma solução cujo custo está garantidamente a um determinado fator de distância do custo da solução ótima. Infelizmente, não existe uma fórmula para se construir algoritmos para problemas de otimização combinatória e muito menos para provar o fator de aproximação do mesmo. O objetivo desse projeto é introduzir o aluno à pesquisa na área de Otimização Combinatória por meio do estudo de diferentes algoritmos clássicos de aproximação e suas técnicas. | |