## 3.5.1 COTAS DE RENDIMIENTO ALGORITMOS DE APROXIMACIÓN

Existen muchos problemas de optimizacion que siendo NP-Completo se necesitan resolver. Entonces, no se puede renunciar a tratar de dar alguna solucion. Las alternativas para lidear con estos problema son :

- Uso de busqueda de fuerza bruta: Incluso para computadoras paralelos rápidas, éste enfoque es viable solo para instancias pequeñas del problema.
- Heurísticas: Una heurística es una estrategia para producir un solucion válida, pero que no garantiza que tan cerca es del óptimo. Esto es viable si todo lo demás falla y si no es un problema tan grande el hecho de no encontrar un óptimo.
- Metodos de búsqueda general: Estos métodos han sido desarrollados en el área de Inteligencia Artificial e investigación de operaciones. Ejemplos de estos métodos son algoritmos genéticos, simulated annealing, A*-search, y branch-and-bound. El rendimiento de estos métodos varía de un problema a otro.
- Algoritmos de aproximacion: Es un algoritmo que corre en tiempo polinomial (idealmente) y que produce una solucion que está dentro de un factor garantizado de la solución optima.

La mayoría de los problemas NP-Completos han sido establecidos como problemas de decisión por razones teóricas; sin embargo, encubren en muchos casos problemas de optimización. Por ejemplo, el Vertex-Cover (el subconjunto de vertices tal que cada arco del grafo es incidente a al menos uno de los vertices en el conjunto) es un problema de optimización que encuentra una cobertura de vértices de tamaño menor y el problema de optimización cliqué es el problema (encontrar el subconjunto de vertices de un grafo que están completamente conectados) de encontrar el cliqué de tamaño máximo. En algunos casos se maximiza y en otros se minimiza.

¿Como se mide qué tan bueno es un algoritmo de aproximación?

Se define una razon de aproximación de un algoritmo de aproximación como sigue. Se asumen:

(1) cada solución potencial tiene un costo positivo asociado y,

(2) el problema puede ser de minimización o maximización del costo.

Dada una instancia I de un problema, sea C(I) el costo de la solución producida por el algoritmo de aproximacion y sea C*(I) el costo de la solución óptima. Se asume que los costos son estrictamente positivos. Para problemas de minimización, se quiere que C(I)/C*(I) sea chico, y para problemas de maximización se quiere que C*(I)/C(I) sea chico. Se dice que para un tamaño de entrada n, el algoritmo de aproximación alcanza una razón de aproximación ρ(n), si para todo I, |I| = n tenemos max ( C(I)/ C*(I) , C*(I) / C(I) ) ≤ ρ(n) Si se cumple la condicion anterior, se dice que el algoritmo es un algoritmo de ρ(n)−aproximación.

En problemas de maximización: 0 ≤ C ≤ C* y ρ(n) = C*/C.

En problemas de minimización: 0 ≤ C* ≤ C y ρ(n) = C/C*.

ρ(n) es siempre positivo.

###