Algoritmo de aproximación

Clase de algoritmos que encuentran soluciones aproximadas a problemas de optimización.

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]

Introducción

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. ${\displaystyle 1+\epsilon }$ ${\displaystyle \epsilon >0}$

Técnicas de diseño de algoritmos.

Actualmente existen varias técnicas establecidas para diseñar algoritmos de aproximación. Estos incluyen los siguientes.

1. Algoritmo codicioso
2. Busqueda local
3. Enumeración y programación dinámica (que también se utiliza a menudo para aproximaciones parametrizadas )
4. Resolver una relajación de programación convexa para obtener una solución fraccionaria. Luego, convertir esta solución fraccionaria en una solución factible mediante un redondeo apropiado. Las relajaciones populares incluyen las siguientes.
   • Relajaciones de programación lineal
   • Relajaciones de programación semidefinidas
5. Métodos duales primarios
6. Montaje doble
7. Incrustar el problema en alguna métrica y luego resolver el problema en esa métrica. Esto también se conoce como incrustación métrica.
8. Muestreo aleatorio y uso de la aleatoriedad en general junto con los métodos anteriores.

Garantías a posteriori

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).

Dureza de aproximación

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 menor que 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 en ese momento no se disponía de una comprensión sistemática. 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]

Sentido práctico

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 que no se pueden utilizar "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] ${\displaystyle n^{O(1/\epsilon )}}$ ${\displaystyle 1+\epsilon }$ ${\displaystyle O(n\log n)}$ ${\displaystyle \epsilon >0}$

Garantías de desempeño

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.

${\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}}$

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

${\displaystyle (\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).}$

De manera similar, la garantía de desempeño , R ( x,y ), de una solución y para una instancia x se define como

${\displaystyle R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),}$

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. ${\displaystyle r=\rho ^{-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: ${\displaystyle \mathrm {P} _{A}}$ ${\displaystyle R_{A}(x)}$

${\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}$

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: ${\displaystyle \mathrm {P} _{A}}$ ${\displaystyle R_{A}^{\infty }}$

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

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.

Términos épsilon

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.

Ver también

• El análisis de dominación considera garantías en términos del rango de la solución calculada.
• PTAS : un tipo de algoritmo de aproximación que toma la relación de aproximación como parámetro
• Algoritmo de aproximación parametrizado : un tipo de algoritmo de aproximación que se ejecuta en tiempo FPT
• APX es la clase de problemas con algún algoritmo de aproximación de factor constante
• Reducción que preserva la aproximación
• Algoritmo exacto

Citas

1. Bernard., Shmoys, David (2011). El diseño de algoritmos de aproximación. Prensa de la Universidad de Cambridge. ISBN 9780521195270. OCLC  671709856.{{cite book}}: CS1 maint: multiple names: authors list (link)
2. Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1 de enero de 1990). "Algoritmos de aproximación para programar máquinas paralelas no relacionadas". Programación Matemática . 46 (1–3): 259–271. CiteSeerX 10.1.1.115.708 . doi :10.1007/BF01585745. ISSN  0025-5610. S2CID  206799898. 
3. Agrawal, Ajit; Klein, Felipe; Ravi, R. (1991). "Cuando los árboles chocan". Actas del vigésimo tercer simposio anual de ACM sobre teoría de la informática - STOC '91 . Nueva Orleans, Luisiana, Estados Unidos: ACM Press. págs. 134-144. doi :10.1145/103418.103437. ISBN 978-0-89791-397-3. S2CID  1245448.
4. Goemans, Michel X.; Williamson, David P. (noviembre de 1995). "Algoritmos de aproximación mejorados para problemas de satisfacción y corte máximo mediante programación semidefinida". J. ACM . 42 (6): 1115-1145. CiteSeerX 10.1.1.34.8500 . doi :10.1145/227683.227684. ISSN  0004-5411. S2CID  15794408. 
5. Khot, Subhash; Regev, Oded (1 de mayo de 2008). "La cobertura de vértices puede ser difícil de aproximar dentro de 2 − ε". Revista de Ciencias de la Computación y de Sistemas . Complejidad computacional 2003. 74 (3): 335–349. doi : 10.1016/j.jcss.2007.06.019 .
6. Karpinski, Marek; Lampis, Michael; Schmied, Richard (1 de diciembre de 2015). "Nuevos límites de inaccesibilidad para TSP". Revista de Ciencias de la Computación y de Sistemas . 81 (8): 1665-1677. arXiv : 1303.6437 . doi :10.1016/j.jcss.2015.06.003.
7. Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (marzo de 1996). "Pruebas interactivas y la dureza de las camarillas aproximadas". J. ACM . 43 (2): 268–292. doi : 10.1145/226643.226652 . ISSN  0004-5411.
8. Arora, Sanjeev; Safra, Shmuel (enero de 1998). "Comprobación probabilística de pruebas: una nueva caracterización de NP". J. ACM . 45 (1): 70-122. doi : 10.1145/273865.273901 . ISSN  0004-5411. S2CID  751563.
9. Johnson, David S. (1 de diciembre de 1974). "Algoritmos de aproximación para problemas combinatorios". Revista de Ciencias de la Computación y de Sistemas . 9 (3): 256–278. doi : 10.1016/S0022-0000(74)80044-9 .
10. Arora, S. (octubre de 1996). "Esquemas de aproximación de tiempo polinómico para TSP euclidiano y otros problemas geométricos". Actas de la 37ª Conferencia sobre fundamentos de la informática . págs. 2-11. CiteSeerX 10.1.1.32.3376 . doi :10.1109/SFCS.1996.548458. ISBN  978-0-8186-7594-2. S2CID  1499391.
11. Arora, S. (octubre de 1997). "Esquemas de aproximación de tiempo casi lineal para TSP euclidiano y otros problemas geométricos". Actas del 38º Simposio Anual sobre Fundamentos de la Informática . págs. 554–563. doi :10.1109/SFCS.1997.646145. ISBN 978-0-8186-8197-4. S2CID  10656723.
12. G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximabilidad .
13. Viggo Kann (1992). Sobre la proximidad de los problemas de optimización NP-completos (PDF) .
14. Johan Hastad (1999). "Algunos resultados óptimos de inaproximabilidad". Revista de la ACM . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . doi :10.1145/502090.502098. S2CID  5120748. 

Referencias

• Vazirani, Vijay V. (2003). Algoritmos de aproximación . Berlín: Springer. ISBN 978-3-540-65367-7.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capítulo 35: Algoritmos de aproximación, págs. 1022-1056. 
• Dorit S. Hochbaum , ed. Algoritmos de aproximación para problemas NP-Hard , PWS Publishing Company, 1997. ISBN 0-534-94968-1 . Capítulo 9: Varias nociones de aproximaciones: bueno, mejor, mejor y más 
• Williamson, David P .; Shmoys, David B. (26 de abril de 2011), El diseño de algoritmos de aproximación , Cambridge University Press , ISBN 978-0521195270

enlaces externos

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski y Gerhard Woeginger , Un compendio de problemas de optimización NP.