Algoritmo de aproximação

Em resposta à resistência computacional de problemas NP-difíceis, os algoritmos de aproximação buscam perder o foco do encontro de um ponto ótimo, seja máximo ou mínimo, de uma função sobre um certo domínio finito em detrimento do ganho de eficiência. O algoritmo garante encontrar de maneira eficiente um elemento pertencente ao domínio de tal forma que este apresente uma relação com o valor ótimo.:1-2 Contudo, 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). 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).

A ideia foi utilizada de forma implícita por R. L. Graham em 1966 quando se tratou de um problema de escalonamento de máquinas, mas foi no início da década de 70 que o conceito foi formalizado. Na década de 1990, a ciência passou a tratar o estudo de forma mais sistemática.:1-2

Algoritmo de aproximação para o problema de cobertura de vértices., produz uma cobertura de vértices que nunca é mais que duas vezes o tamanho de uma das menores coberturas de vértice. A = "Sobre a entrada <G>, onde G é um grafo não-direcionado:

Para alguns algoritmos de aproximação, é possível provar certas propriedades sobre a aproximação do resultado. Por exemplo, no caso de um algoritmo de aproximação-ρ A provou-se que o custo f(x), da solução aproximada A(x) sendo x um exemplo, não será maior (ou menor, dependendo da situação) do que algumas vezes ρ o valor OTM (valor de uma solução ótima). O fator ρ é chamado de garantia relativa de desempenho. Um algoritmo de aproximação tem uma garantia de desempenho absoluto limitada por um erro C, se tiver sido comprovada para cada instancia de x que: Do mesmo modo, a garantia de desempenho R (x, y) de uma solução y para um exemplo x é definida como: Onde f(y) é o custo da solução y para o exemplo x. Claramente, a garantia de desempenho é maior ou igual a 1 se e somente se y é uma solução ótima. Se a garantia de um Algoritmo A retorna uma garantia de desempenho de no máximo r(n), então A é dito um algoritmo de r(n)- aproximação. Da mesma forma, um problema com um algoritmo de r(n)-aproximação é dito ser r(n)-aproximável ou têm uma relação de aproximação r(n).

Na literatura, uma taxa de aproximação para um problema de maximização/minimização de c - ϵ (min: c + ϵ), significa que este algoritmo tem uma taxa de aproximação de c ∓ ϵ com ϵ > 0. Um termo ϵ pode aparecer quando um algoritmo de aproximação introduz um erro multiplicativo ou constante, enquanto o mínimo ideal de instancias de tamanho n vão para o infinito. Neste caso, a taxa de aproximação é c ∓ k/ OTM = c ∓ o(1) para alguma constante c e k. Dado um ϵ > 0 qualquer, pode-se escolher um valor N tal que k/ OTM < ϵ para todo n ≥ N. Para toda constante ϵ, instancias n < N podem ser resolvidas por força bruta, mostrando a existencia de um algoritmo de aproximação com a garantia de c ∓ ϵ para todo ϵ > 0.