Busca avançada
Ano de início
Entree

Algoritmos de aproximação

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.