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 , 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 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 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(n2000). 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 ).