Algoritmos de aproximação

• Processo: 19/13311-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2019
• Data de Término da vigência: 31 de agosto de 2020
• Área de 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
• Palavra(s)-Chave do Pesquisador: Algoritmos | Algoritmos de Aproximação | Otimização Combinatória | Projeto e Análise de Algoritmos | Algoritmos de aproximação

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.