Algoritmo de aproximación

En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP-hard; como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-hard, se opta por encontrar soluciones no-óptimas en tiempo polinomial. A diferencia de las heurísticas, que usualmente solo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca aquí es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotadas por cotas conocidas. Idealmente, la aproximación mejora su calidad para factores constantes pequeños (por ejemplo, dentro del 5% de la solución óptima). Los algoritmos de aproximación están siendo cada vez más utilizados para resolver problemas donde los algoritmos exactos de tiempo polinomial son conocidos pero demasiado costosos debido al tamaño de la entrada.

Un ejemplo típico para un algoritmo de aproximación es uno para resolver el problema de la cobertura de vértices de la teoría de grafos: encontrar una arista no cubierta y añadir sus dos puntos finales a la cobertura de vértice, y repetir hasta que ya no queden aristas. Es claro que la cobertura resultante será a lo más dos veces del largo de la solución óptima. Este es un algoritmo de aproximación de factor constante con un factor de 2.

Los problemas NP-hard varían mucho en su aproximación; algunos, tales como el problema de la mochila, pueden ser aproximados mediante cualquier factor superior a 1 (tal familia de algoritmos de aproximación se conoce como esquema de aproximación de tiempo polinomial o PTAS). Otros, como el problema de la clique, son imposibles de aproximar dentro de cualquier constante, o incluso factor polinomiales, a menos que P = NP.

Los problemas NP-hard frecuentemente pueden expresarse como programación entera (PE) y ser resueltos exactamente en tiempo exponencial. Muchos algoritmos de aproximación surgen de la relajación de la programación lineal (PL), propia de la programación entera.

No todos los algoritmos de aproximación son adecuados para todas las aplicaciones prácticas. A menudo utilizan resolvedores (solvers) de IP, LP y programación semidefinida, estructuras de datos complejas o técnicas de algoritmos sofisticadas que tienden a dificultar los problemas de implementación. Además, algunos algoritmos de aproximación poseen tiempos de ejecución poco prácticos, incluso a pesar de ser polinómicos, como por ejemplo, del orden de O(n²⁰⁰⁰). Sin embargo, a pesar de esto último, existen problemas donde los altos tiempos de ejecución y costos de memoria pueden justificarse, tales como los relacionados con la biología computacional, ingeniería financiera, la planificación del transporte, y la gestión de inventario. En estos escenarios, se debe competir contra las correspondientes formulaciones de programación entera directa.

Otra limitación de la aproximación es que esta solo es aplicable a los problemas de optimización, y no a los problemas de decisión en estado "puro", tales como SAT (a pesar de que es posible representar versiones de optimización para tales problemas, como el respectivo Problema de satisfacibilidad máximo).

Garantías de comportamiento

Para algunos algoritmos de aproximación es posible demostrar con certeza propiedades sobre la aproximación del resultado óptimo. Por ejemplo, en el caso de un ρ-algoritmo de aproximación se ha demostrado que la aproximación a no será mayor (o menor, dependiendo de la situación) que un factor ρ veces la solución óptima s.

{\begin{cases}s\leq a\leq \rho s,\qquad {\mbox{if }}\rho >1;\\\rho s\leq a\leq s,\qquad {\mbox{if }}\rho <1.\end{cases}}

El factor ρ se llama garantía de comportamiento relativo (relative performance guarantee). Un algoritmo de aproximación tiene una garantía de comportamiento absoluto o error acotado ε, si se ha demostrado que

(s-\epsilon )\leq a\leq (s+\epsilon ).

Análogamente, el radio de comportamiento aboluto (absolute performance ratio) $\mathrm {P} _{A}$ de un algoritmo de aproximación $A$ , donde $I$ es una instancia del problema, y $R_{A}(I)$ es la garantía de comportamiento de $A$ en $I$ (es decir, $\rho$ para la instancia $I$ del problema) es:

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

Esto significa que $\mathrm {P} _{A}$ es la mayor cota en el radio de aproximación, $r$ , que uno encuentra en todas las posibles instancias del problema. Del mismo modo, el radio de comportamiento asintótico (asymptotic performance ratio) $R_{A}^{\infty }$ es:

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

Es decir, que es el mismo radio de comportamiento absoluto, con una cota inferior $n$ en el tamaño de las instancias del problema. Se utilizan estos dos tipos de radio porque debido a que existen algoritmos donde la diferencia entre ellos es significativa.

El análisis de dominación (Domination analysis) provee un camino alternativo para analizar la calidad de un algoritmo de aproximación, en términos del rango de la solución computada en la secuencia ordenada de todas las posibles soluciones.

Referencias

Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3540653678.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, y Clifford Stein. Introduction to Algorithms, Segunda Edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7. Capítulo 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. Capítulo 9: Various Notions of Approximations: Good, Better, Best, and More.

Enlaces externos

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

Datos: Q621751