En informática e investigación de operaciones , los algoritmos de aproximación son algoritmos eficientes que encuentran soluciones aproximadas a problemas de optimización (en particular problemas NP-difíciles ) con garantías demostrables sobre la distancia de la solución devuelta 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 . Según esta conjetura, una amplia clase de problemas de optimización no pueden resolverse exactamente en tiempo polinomial . Por lo tanto, el campo de los algoritmos de aproximación intenta comprender qué tan cerca es posible aproximar las 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 relació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 proporcionan 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] para programación en máquinas paralelas no relacionadas.
El diseño y análisis de algoritmos de aproximación implica fundamentalmente 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 ninguna indicación clara desde el principio sobre cuándo pueden tener éxito o fracasar.
Existe un interés generalizado en la informática teórica para comprender mejor los límites a los que podemos aproximarnos a ciertos problemas de optimización famosos. Por ejemplo, una de las preguntas abiertas desde hace mucho tiempo en informática es determinar si existe un algoritmo que supere la aproximación 2 para el problema del bosque de Steiner de Agrawal et al. [3] El deseo de comprender los problemas de optimización difíciles desde la perspectiva de la aproximación 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 bien conocido del primero es el algoritmo de Goemans-Williamson para corte máximo , que resuelve un problema de teoría de grafos utilizando geometría de alta dimensión. [4]
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 manera que cada arista 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: encontrar un borde descubierto, agregar ambos extremos a la cobertura y eliminar todos los bordes incidentes en 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 máximo el doble de la óptima. En otras palabras, este es un algoritmo de aproximación de factor constante con un factor de aproximación de 2. Según la reciente conjetura de los juegos únicos , este factor es incluso el mejor posible. [5]
Los problemas NP-difíciles varían mucho en su aproximación; algunos, como el problema de la mochila , pueden aproximarse dentro de un factor multiplicativo , para cualquier valor fijo , y por lo tanto producen soluciones arbitrariamente cercanas al óptimo (esta familia de algoritmos de aproximación se denomina esquema de aproximación en tiempo polinomial o PTAS). Otros son imposibles de aproximar dentro de cualquier factor constante, o incluso polinómico, a menos que P = NP , como en el caso del problema de camarilla máxima . Por lo tanto, un beneficio importante de estudiar algoritmos de aproximación es una clasificación detallada de la dificultad de varios problemas NP-difíciles más allá de la que ofrece la teoría de la completitud NP . En otras palabras, aunque los problemas NP-completos pueden ser equivalentes (bajo reducciones de tiempo polinomiales) entre sí desde la perspectiva de las soluciones exactas, los problemas de optimización correspondientes se comportan de manera muy diferente desde la perspectiva de las soluciones aproximadas.
Actualmente existen varias técnicas establecidas para diseñar algoritmos de aproximación. Estos incluyen los siguientes.
Si bien los algoritmos de aproximación siempre proporcionan una garantía a priori del peor de los casos (ya sea aditiva o multiplicativa), en algunos casos también proporcionan una garantía a posteriori que suele ser mucho mejor. Este suele ser el caso de los algoritmos que funcionan resolviendo una relajación convexa del problema de optimización en la entrada dada. Por ejemplo, existe un algoritmo de aproximación diferente para la cobertura mínima de vértice que resuelve una relajación de programación lineal para encontrar una cobertura de vértice que sea como máximo el doble del valor de la relajación. Dado que el valor de la relajación nunca es mayor que el tamaño de la cobertura de vértice óptima, esto produce otro algoritmo de 2 aproximaciones. Si bien esto es similar a la garantía a priori del algoritmo de aproximación anterior, la garantía de este último puede ser mucho mejor (de hecho, cuando el valor de la relajación LP está lejos del tamaño de la cobertura de vértice óptima).
Los algoritmos de aproximación como área de investigación están estrechamente relacionados e informados por la teoría de la inaproximabilidad, donde se prueba la inexistencia de algoritmos eficientes con ciertos ratios de aproximación (condicionados a hipótesis ampliamente creídas como la conjetura P ≠ NP) mediante reducciones . En el caso del problema métrico del viajante, el resultado de inaproximabilidad más conocido descarta algoritmos con una relación de aproximación inferior a 123/122 ≈ 1,008196 a menos que P = NP, Karpinski, Lampis, Schmied. [6] Junto con el conocimiento de la existencia del algoritmo de aproximación 1,5 de Christofides, esto nos dice que el umbral de aproximabilidad para el viajante de comercio métrico (si existe) está entre 123/122 y 1,5.
Si bien se han demostrado resultados de inaccesibilidad desde la década de 1970, dichos resultados se obtuvieron por medios ad hoc y no se disponía de una comprensión sistemática en ese momento. Sólo a partir del resultado de 1990 de Feige, Goldwasser, Lovász, Safra y Szegedy sobre la inaproximabilidad del conjunto independiente [7] y el famoso teorema PCP , [8] se descubrieron herramientas modernas para demostrar resultados de inaproximabilidad. El teorema PCP, por ejemplo, muestra que los algoritmos de aproximación de Johnson de 1974 para Max SAT , cobertura de conjuntos , conjunto independiente y coloración logran la relación de aproximación óptima, suponiendo que P ≠ NP. [9]
No todos los algoritmos de aproximación son adecuados para aplicaciones prácticas directas. Algunos implican resolver programación lineal no trivial / relajaciones semidefinidas (que pueden invocar el algoritmo elipsoide ), estructuras de datos complejas o técnicas algorítmicas sofisticadas, lo que lleva a problemas de implementación difíciles o a un mejor rendimiento del tiempo de ejecución (en comparación con algoritmos exactos) solo en entradas imprácticamente grandes. . Dejando a un lado los problemas de implementación y tiempo de ejecución, las garantías proporcionadas por los algoritmos de aproximación pueden no ser lo suficientemente sólidas como para justificar su consideración en la práctica. A pesar de su imposibilidad de utilizarse "de forma inmediata" en aplicaciones prácticas, las ideas y conocimientos detrás del diseño de tales algoritmos a menudo pueden incorporarse de otras maneras en algoritmos prácticos. De esta manera, el estudio de algoritmos, incluso muy costosos, no es una actividad completamente teórica, ya que pueden arrojar conocimientos valiosos.
En otros casos, incluso si los resultados iniciales son de interés puramente teórico, con el tiempo, con una mejor comprensión, los algoritmos pueden perfeccionarse para volverse más prácticos. Un ejemplo de ello es el PTAS inicial para TSP euclidiano de Sanjeev Arora (e independientemente de Joseph Mitchell ), que tenía un tiempo de ejecución prohibitivo para una aproximación. [10] Sin embargo, al cabo de un año estas ideas se incorporaron a un algoritmo de tiempo casi lineal para cualquier constante . [11]
Dado un problema de optimización:
donde es un problema de aproximación, el conjunto de insumos y el conjunto de soluciones, podemos definir la función de costos:
y el conjunto de soluciones factibles:
Encontrar la mejor solución para un problema de maximización o minimización:
,
Dada una solución factible , con , querríamos una garantía de la calidad de la solución, que es un rendimiento a garantizar (factor de aproximación).
Específicamente, teniendo el algoritmo tiene un factor de aproximación (o relación de aproximación ) de si , tenemos:
Se puede demostrar que la aproximación es ajustada ( aproximación ajustada ) demostrando que existen casos en los que el algoritmo funciona en el límite de aproximación, lo que indica la rigidez del límite. En este caso, es suficiente construir una instancia de entrada diseñada para forzar al algoritmo a entrar en el peor de los casos.
Para algunos algoritmos de aproximación es posible demostrar ciertas propiedades sobre la aproximación del resultado óptimo. Por ejemplo, un algoritmo de aproximación ρ A se define como un algoritmo para el cual se ha demostrado que el valor/coste, f ( x ), de la solución aproximada A ( x ) para una instancia x no será mayor (o menos, dependiendo de la situación) que un factor ρ multiplicado por el valor, OPT, de una solución óptima.
El factor ρ se llama garantía de desempeño relativo . Un algoritmo de aproximación tiene una garantía de rendimiento absoluta o un error acotado c , si se ha demostrado para cada instancia x que
De manera similar, la garantía de desempeño , R ( x,y ), de una solución y para una instancia x se define como
donde f ( y ) es el valor/costo de la solución y para la instancia x . Claramente, la garantía de desempeño es mayor o igual a 1 e igual a 1 si y sólo si y es una solución óptima. Si un algoritmo A garantiza devolver soluciones con una garantía de rendimiento de como máximo r ( n ), entonces se dice que A es un algoritmo de aproximación r ( n ) y tiene una relación de aproximación de r ( n ). Del mismo modo, se dice que un problema con un algoritmo de aproximación r ( n ) es r ( n ) - aproximable o que tiene una relación de aproximación de r ( n ). [12] [13]
Para problemas de minimización, las dos garantías diferentes proporcionan el mismo resultado y para problemas de maximización, una garantía de desempeño relativa de ρ es equivalente a una garantía de desempeño de . En la literatura, ambas definiciones son comunes pero está claro cuál se utiliza ya que, para problemas de maximización, como ρ ≤ 1 mientras que r ≥ 1.
La garantía de rendimiento absoluta de algún algoritmo de aproximación A , donde x se refiere a una instancia de un problema, y donde está la garantía de rendimiento de A en x (es decir, ρ para la instancia de problema x ) es:
Es decir, es el límite más grande de la relación de aproximación, r , que se ve en todas las instancias posibles del problema. Asimismo, el índice de rendimiento asintótico es:
Es decir, es lo mismo que el índice de rendimiento absoluto , con un límite inferior n en el tamaño de las instancias del problema. Estos dos tipos de ratios se utilizan porque existen algoritmos donde la diferencia entre estos dos es significativa.
En la literatura, una relación de aproximación para un problema de maximización (minimización) de c - ϵ (min: c + ϵ) significa que el algoritmo tiene una relación de aproximación de c ∓ ϵ para ϵ > 0 arbitrario pero que la relación no tiene (o no) se puede mostrar para ϵ = 0. Un ejemplo de esto es la relación óptima de inaproximabilidad (inexistencia de aproximación) de 7/8 + ϵ para instancias MAX-3SAT satisfactorias debido a Johan Håstad . [14] Como se mencionó anteriormente, cuando c = 1, se dice que el problema tiene un esquema de aproximación de tiempo polinomial .
Un término ϵ puede aparecer cuando un algoritmo de aproximación introduce un error multiplicativo y un error constante mientras que el óptimo mínimo de instancias de tamaño n llega al infinito como lo hace n . En este caso, la relación de aproximación es c ∓ k / OPT = c ∓ o(1) para algunas constantes c y k . Dado ϵ > 0 arbitrario, se puede elegir un N lo suficientemente grande como para que el término k / OPT < ϵ para cada n ≥ N. Para cada ϵ fijo, los casos de tamaño n < N pueden resolverse mediante fuerza bruta, mostrando así una relación de aproximación (existencia de algoritmos de aproximación con garantía) de c ∓ ϵ para cada ϵ > 0.
{{cite book}}
: CS1 maint: multiple names: authors list (link)