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.