Gabarito C
Um algoritmo de aproximação para um problema de otimização é um algoritmo eficiente (polinomial) que produz uma solução com garantia de qualidade, ou seja, uma solução cujo valor não é pior que uma fração pré-determinada do ótimo. (Assim, um algoritmo de aproximação é mais que uma meraheurística, que não dá qualquer garantia sobre a qualidade da solução.)
Considere, por exemplo, o problema de encontrar uma clique máxima num grafo. Um algoritmo de aproximação típico produz uma clique de tamanho pelo menos 50% do máximo. Dizemos que um tal algoritmo tem razão de aproximação 2 (pois 2×50% = 100%).
Para a grande maioria dos problemas de otimização interessantes não se conhecem algoritmos exatos eficientes. Para esses problemas os algoritmos de aproximação são muito úteis.
Nem todo problema de otimização admite algoritmo de aproximação. Para certos problemas, encontrar uma solução aproximada é tão difícil quanto encontrar uma solução ótima.
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !