En ciencias de la computación y la investigación de operaciones , algoritmos de aproximación son eficientes algoritmos que encuentran aproximados soluciones a los problemas de optimización (en particular, NP-duros problemas) con garantías demostrables sobre la distancia de la solución vuelto a la óptima. [1] Los algoritmos de aproximación surgen naturalmente en el campo de la informática teórica como consecuencia de la conjetura P ≠ NP ampliamente creída . Bajo esta conjetura, una amplia clase de problemas de optimización no se pueden resolver exactamente en tiempo polinomial.. El campo de los algoritmos de aproximación, por lo tanto, intenta comprender qué tan cerca es posible aproximar soluciones óptimas a tales problemas en tiempo polinomial. En una abrumadora mayoría de los casos, la garantía de tales algoritmos es multiplicativa expresada como una razón de aproximación o factor de aproximación, es decir, siempre se garantiza que la solución óptima estará dentro de un factor multiplicativo (predeterminado) de la solución devuelta. Sin embargo, también existen muchos algoritmos de aproximación que brindan una garantía aditiva sobre la calidad de la solución devuelta. Un ejemplo notable de un algoritmo de aproximación que proporciona ambos es el algoritmo de aproximación clásico de Lenstra , Shmoys y Tardos [2] paraprogramación en máquinas paralelas no relacionadas.
El diseño y análisis de algoritmos de aproximación implica de manera crucial una prueba matemática que certifique la calidad de las soluciones devueltas en el peor de los casos. [1] Esto los distingue de heurísticas como el recocido o los algoritmos genéticos , que encuentran soluciones razonablemente buenas en algunas entradas, pero no proporcionan una indicación clara desde el principio de cuándo pueden tener éxito o fallar.
Existe un interés generalizado en la informática teórica para comprender mejor los límites a los que podemos aproximar ciertos problemas de optimización famosos. Por ejemplo, una de las preguntas abiertas desde hace mucho tiempo en la informática es determinar si existe un algoritmo que supere el algoritmo de aproximación 1.5 de Christofides al problema métrico del vendedor ambulante . El deseo de comprender los problemas de optimización difíciles desde la perspectiva de la aproximabilidad está motivado por el descubrimiento de conexiones matemáticas sorprendentes y técnicas ampliamente aplicables para diseñar algoritmos para problemas de optimización difíciles. Un ejemplo conocido del primero es el algoritmo de Goemans-Williamson para un corte máximo, que resuelve un problema de teoría de grafos utilizando geometría de alta dimensión. [3]
Un ejemplo simple de un algoritmo de aproximación es uno para el problema de cobertura mínima de vértices , donde el objetivo es elegir el conjunto más pequeño de vértices de modo que cada borde en el gráfico de entrada contenga al menos un vértice elegido. Una forma de encontrar una cobertura de vértice es repetir el siguiente proceso: busque un borde descubierto, agregue ambos puntos finales a la cobertura y elimine todos los bordes incidentes a cualquiera de los vértices del gráfico. Como cualquier cobertura de vértice del gráfico de entrada debe usar un vértice distinto para cubrir cada borde que se consideró en el proceso (ya que forma una coincidencia ), la cobertura de vértice producida, por lo tanto, es como mucho dos veces más grande que la óptima. En otras palabras, este es un algoritmo de aproximación de factor constante con un factor de aproximación de 2. Bajo el recienteConjetura de juegos únicos , este factor es incluso el mejor posible. [4]