algoritmo de aproximação

Em ciências da computação e pesquisa operacional (PO), algoritmos de aproximação são algoritmos usados para encontrar soluções aproximadas em problemas de otimização. Algoritmos de aproximação são geralmente associados com problemas NP-difíceis, já que estes problemas não podem ser resolvidos em tempo polinomial. Também em alguns problemas resolvidos em tempo polinomial no qual o tamanho da entrada pode fazer com que mesmo algoritmos polinomiais sejam custosos, estão sendo cada vez mais usados algoritmos de aproximação. Na prática, podemos não precisar da solução ótima do problema, uma solução boa obtida por um algoritmo de aproximação pode ser suficientemente e mais fácil de ser obtida. Uma outra saída para estes problemas são as Heurísticas, entretanto essas normalmente encontram soluções razoavelmente boas, com uma velocidade não muito boa. Idealmente, a aproximação é ótima até um pequeno fator constante (geralmente de 5% da solução ótima). Diferentes problemas NP-dificeis possuem níveis diferentes de aproximação. Por exemplo, o problema pode ser aproximado com qualquer fator maior que 1, já outros não podem ser aproximados dentro de qualquer constante ou fator polinomial, ao menos que P = NP, como, por exemplo, o problema clique. Um grupo de algoritmos de aproximação são chamados de Esquema de aproximação em tempo polinomial ou PTAS. Nem todos os algoritmos de aproximação são usuais na prática. Eles costumam usar estruturas de dados complexos ou sofisticadas técnicas algorítmicas que dificultam sua implementação. Além disso, alguns algoritmos de aproximação tem tempos de execução não viaveis, embora sejam de tempo polinomial, por exemplo, O(n2000). No entanto, o estudo de alguns algoritmos mesmo muito caros podem fornecer conhecimentos valiosos. Um exemplo clássico é o PTAS para o problema do caxeiro viajante euclidiano (PCV euclidiano, problema PCV utilizando distâncias euclidianas) concebido por Sanjeev Arora, que possui um tempo de execução de um ano, redefinindo os conceitos de algoritmo de tempo linear. Esses algoritmos são úteis em algumas aplicações onde os tempos de execução e de custo podem ser justificados, como por exemplo: biologia computacional, engenharia financeira, planejamento, transporte e gerenciamento de inventário. Outra limitação da abordagem é que ela se aplica somente a problemas de otimização e não a problemas de decisão em essência como o problema da satisfatibilidade, embora muitas vezes é possível conceber versões de otimização de tais problemas. (Max SAT).