Algoritmo de aproximação

Em ciência 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(n²⁰⁰⁰). 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).

Exemplo de algoritmo de aproximação

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:

1. Repita o seguinte até que todas as arestas em G toquem uma aresta marcada:
   
2. Encontre uma aresta em G não tocada por nenhuma aresta marcada
   
3. Marque essa aresta
   
4. Dê como saída todos os nós que são extremidades de arestas marcadas"

Garantias de desempenho

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).

${\begin{cases}\mathrm {OTM} \leq f(x)\leq \rho \mathrm {OTM} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OTM} \leq f(x)\leq \mathrm {OTM} ,\qquad {\mbox{if }}\rho <1.\end{cases}}$

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:

$(\mathrm {OTM} -c)\leq f(x)\leq (\mathrm {OTM} +c).$

Do mesmo modo, a garantia de desempenho R (x, y) de uma solução y para um exemplo x é definida como:

R(x,y) = $\max \left({\frac {OTM}{f(y)}},{\frac {f(y)}{OTM}}\right),$

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).

Pode-se notar que para problemas de minimização as duas garantias fornecem o mesmo resultado e que para problemas de maximização, uma garantia relativa de desempenho de ρ é equivalente a uma garantia de desempenho de $r=\rho ^{-1}$.

A garantia absoluta de desempenho $\mathrm {P} _{A}$ de um algoritmo de aproximação A, onde x é a instância de um problema, e $R_{A}(x)$ a garantia de desempenho de A em x (por exemplo ρ para o problema anterior) é:

$\mathrm {P} _{A}=\inf\{r\geq 1\,|\,R_{A}(I)\leq r,\forall x\}.$

Isto quer dizer que $\mathrm {P} _{A}$ é o limite superior da taxa de aproximação r, presentes em todas as instâncias possíveis do problema. Da mesma forma, a taxa de desempenho assintótico $R_{A}^{\infty }$ é:

$R_{A}^{\infty }=\inf\{r\geq 1\,|\,\exists n\in \mathbb {Z} ^{+},R_{A}(I)\leq r,\forall x,|x|\geq n\}.$

Isto quer dizer que é o mesmo que a taxa de desempenho absoluto, com limite inferior n, o tamanho da instância do problema. Estas duas taxas são utilizadas porque em alguns algoritmos onde a diferença entre elas é significativa.

Garantias de desempenho

	r-aprox	ρ-aprox	erro rel.	erro rel.	erro norm.rel.	erro abs.
max: $f(x)\geq$	$r^{-1}\mathrm {OTM}$	$\rho \mathrm {OTM}$	$(1-c)\mathrm {OTM}$	$(1-c)\mathrm {OTM}$	$(1-c)\mathrm {OTM} +c\mathrm {PIOR}$	$\mathrm {OTM} -c$
min: $f(x)\leq$	$r\mathrm {OTM}$	$\rho \mathrm {OTM}$	$(1+c)\mathrm {OTM}$	$(1-c)^{-1}\mathrm {OTM}$	$(1-c)^{-1}\mathrm {OTM} +c\mathrm {PIOR}$	$\mathrm {OTM} +c$

Termos epsilon

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.

Veja também

Domination analysis considerando garantias em termos de classificação de uma solução em computação.

Referências

• Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8 

• Sipsel, Michael (2007). Introdução à teoria da computação. São Paulo: Cengage Learning. ISBN 978-85-221-0499-4 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 35: Approximation Algorithms, pp. 1022–1056.
• Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More

Ligações externas

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.