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-hard ) 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 aceptada . 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 aproximarse a soluciones óptimas para 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 esté dentro de un factor multiplicativo (predeterminado) de la solución devuelta. Sin embargo, también hay 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 ambas cosas es el algoritmo de aproximación clásico de Lenstra , Shmoys y Tardos ^[2] para la 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 obtenidas en el peor de los casos. ^[1] Esto los distingue de las 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 sobre cuándo pueden tener éxito o fracasar.

Existe un interés generalizado en la informática teórica por 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 la 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 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 bien conocido del primero es el algoritmo de Goemans-Williamson para el 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 modo que cada arista en el grafo de entrada contenga al menos un vértice elegido. Una forma de encontrar una cobertura de vértices es repetir el siguiente proceso: encontrar una arista descubierta, agregar ambos puntos finales a la cobertura y eliminar todas las aristas incidentes a cualquiera de los vértices del grafo. Como cualquier cobertura de vértices del grafo de entrada debe usar un vértice distinto para cubrir cada arista que se consideró en el proceso (ya que forma un ) , la cobertura de vértices producida, por lo tanto, es como máximo el doble de 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 la reciente conjetura de juegos únicos , este factor es incluso el mejor posible. ^[5]

Los problemas NP-hard varían mucho en su aproximabilidad; algunos, como el problema de la mochila , se pueden aproximar dentro de un factor multiplicativo , para cualquier fijo , y por lo tanto producen soluciones arbitrariamente cercanas al óptimo (una familia de algoritmos de aproximación de este tipo se llama esquema de aproximación de tiempo polinomial o PTAS). Otros son imposibles de aproximar dentro de cualquier factor constante, o incluso polinomial, 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 de grano fino de la dificultad de varios problemas NP-hard más allá de la proporcionada por la teoría de NP-completitud . En otras palabras, aunque los problemas NP-completos pueden ser equivalentes (bajo reducciones de tiempo polinomial) entre sí desde la perspectiva de soluciones exactas, los problemas de optimización correspondientes se comportan de manera muy diferente desde la perspectiva de 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, entre las que se incluyen las siguientes:

1. Algoritmo codicioso
2. Búsqueda 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 adecuado. Las relajaciones más populares incluyen las siguientes.
   • Relajaciones de programación lineal
   • Relajaciones de programación semidefinida
5. Métodos primal-duales
6. Doble ajuste
7. Incorporar el problema en alguna métrica y luego resolver el problema en esa métrica. Esto también se conoce como incorporación de métricas.
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 brindan una garantía a priori del peor caso (ya sea aditivo o multiplicativo), en algunos casos también brindan una garantía a posteriori que a menudo es 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értices que resuelve una relajación de programación lineal para encontrar una cobertura de vértices 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 óptima de vértices, 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 de programación lineal está lejos del tamaño de la cobertura óptima de vértices).

Dureza de aproximación

Los algoritmos de aproximación como área de investigación están estrechamente relacionados con la teoría de la inaproximabilidad y se basan en ella, donde se demuestra la inexistencia de algoritmos eficientes con ciertas razones de aproximación (condicionada a hipótesis ampliamente aceptadas, como la conjetura P ≠ NP) mediante reducciones . En el caso del problema del viajante de comercio métrico, el resultado de inaproximabilidad más conocido descarta algoritmos con una razó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á en algún lugar entre 123/122 y 1.5.

Si bien los resultados de inaproximabilidad se han demostrado desde la década de 1970, dichos resultados se obtuvieron por medios ad hoc y no había una comprensión sistemática disponible en ese momento. Solo 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 la resolución de programas lineales no triviales / relajaciones semidefinidas (que pueden invocar el algoritmo del elipsoide ), estructuras de datos complejas o técnicas algorítmicas sofisticadas, lo que lleva a problemas de implementación difíciles o un mejor rendimiento en tiempo de ejecución (en comparación con algoritmos exactos) solo en entradas imprácticamente grandes. Dejando de 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 incapacidad para usarse "de fábrica" ​​en aplicaciones prácticas, las ideas y los conocimientos detrás del diseño de dichos algoritmos a menudo se pueden incorporar de otras maneras en algoritmos prácticos. De esta manera, el estudio de algoritmos incluso muy costosos no es una búsqueda completamente teórica, ya que pueden brindar información valiosa.

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 refinarse 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 de para una aproximación. ^[10] Sin embargo, en el plazo 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}$

Estructura de los algoritmos de aproximación

Dado un problema de optimización:

${\displaystyle \Pi :I\times S}$

donde es un problema de aproximación, el conjunto de entradas y el conjunto de soluciones, podemos definir la función de costo: ${\displaystyle \Pi }$ ${\displaystyle I}$ ${\displaystyle S}$

${\displaystyle c:S\rightarrow \mathbb {R} ^{+}}$

y el conjunto de soluciones factibles:

${\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}}$

Encontrar la mejor solución para un problema de maximización o minimización: ${\displaystyle s^{*}}$

${\displaystyle s^{*}\in S(i)}$, ${\displaystyle c(s^{*})=min/max\ c(S(i))}$

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). ${\displaystyle s\in S(i)}$ ${\displaystyle s\neq s^{*}}$

En concreto, teniendo , el algoritmo tiene un factor de aproximación (o razón de aproximación ) de si , tenemos: ${\displaystyle A_{\Pi }(i)\in S_{i}}$ ${\displaystyle \rho (n)}$ ${\displaystyle \forall i\in I\ s.t.|i|=n}$

• para un problema de minimización : , lo que a su vez significa que la solución tomada por el algoritmo dividida por la solución óptima logra una relación de ; ${\displaystyle {\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)}$ ${\displaystyle \rho (n)}$
• para un problema de maximización : , lo que a su vez significa que la solución óptima dividida por la solución tomada por el algoritmo logra una relación de ; ${\displaystyle {\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)}$ ${\displaystyle \rho (n)}$

La aproximación se puede demostrar como 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 actuar en el peor de los casos.

Garantías de rendimiento

Para algunos algoritmos de aproximación es posible probar 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 probado que el valor/costo, f ( x ), de la solución aproximada A ( x ) para una instancia x no será mayor (o menor, 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 denomina garantía de rendimiento relativa . 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 rendimiento , 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 rendimiento es mayor o igual a 1 e igual a 1 si y solo 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 razó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 tiene una razón de aproximación de r ( n ). [ ^{12] [13]}

Para los problemas de minimización, las dos garantías diferentes proporcionan el mismo resultado y para los problemas de maximización, una garantía de rendimiento relativa de ρ es equivalente a una garantía de rendimiento de . En la literatura, ambas definiciones son comunes pero está claro cuál definición se utiliza ya que, para los problemas de maximización, ρ ≤ 1 mientras que r ≥ 1. ${\displaystyle r=\rho ^{-1}}$

La garantía de rendimiento absoluto de algún algoritmo de aproximación A , donde x se refiere a una instancia de un problema, y ​​donde es la garantía de rendimiento de A en x (es decir, ρ para la instancia del 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áximo de la razón de aproximación, r , que se observa en todas las instancias posibles del problema. Asimismo, la razón 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 ratio de rendimiento absoluto , con un límite inferior n en el tamaño de las instancias del problema. Se utilizan estos dos tipos de ratios porque existen algoritmos en los que la diferencia entre ambos es significativa.

Términos épsilon

En la literatura, una razón de aproximación para un problema de maximización (minimización) de c - ϵ (mín: c + ϵ) significa que el algoritmo tiene una razón de aproximación de c ∓ ϵ para un ϵ > 0 arbitrario pero que la razón no se ha demostrado (o no se puede demostrar) para ϵ = 0. Un ejemplo de esto es la inaproximabilidad óptima (inexistencia de aproximación) razón de 7 / 8 + ϵ para instancias MAX-3SAT satisfacibles 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 tiende a infinito como lo hace n . En este caso, la razón de aproximación es c ∓ k / OPT = c ∓ o(1) para algunas constantes c y k . Dado un valor arbitrario de ϵ > 0, se puede elegir un N suficientemente grande como para que el término k / OPT < ϵ para cada n ≥ N . Para cada ϵ fijo, las instancias de tamaño n < N se pueden resolver por fuerza bruta, mostrando así una razón de aproximación —existencia de algoritmos de aproximación con garantía— de c ∓ ϵ para cada ϵ > 0.

Véase 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. Cambridge University Press. 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 la planificación de 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, Philip; Ravi, R. (1991). "Cuando los árboles chocan". Actas del vigésimo tercer simposio anual de la ACM sobre teoría de la computación - STOC '91 . Nueva Orleans, Luisiana, Estados Unidos: ACM Press. págs. 134-144. doi :10.1145/103418.103437. ISBN 978-0-89791-397-3.S2CID1245448  .​
4. Goemans, Michel X.; Williamson, David P. (noviembre de 1995). "Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad utilizando 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). "Puede resultar difícil aproximar la cobertura de vértices dentro de 2−ε". Journal of Computer and System Sciences . Computational Complexity 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 inaproximabilidad 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). "Verificació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 temporal polinómica para TSP euclidiano y otros problemas geométricos". Actas de la 37.ª Conferencia sobre Fundamentos de la Ciencia de la Computación . 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 temporal casi lineal para problemas geométricos y de transición de tiempo euclidianos". 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.S2CID10656723  .​
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 aproximabilidad de problemas de optimización NP-completos (PDF) .
14. Johan Håstad (1999). "Algunos resultados de inaproximabilidad óptima". 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: Diversas nociones de aproximaciones: buena, mejor, óptima 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.