Algoritmo de aproximación

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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 al óptimo. uno. 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. 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 para la programació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. 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. 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 de lo 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.

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

Los problemas duros NP varían mucho en su aproximabilidad; algunos, como el problema de la mochila, pueden ser aproximados dentro de un factor multiplicativo ${displaystyle 1+epsilon }$ , para cualquier fijo ${displaystyle epsilon }$ , y por lo tanto producir soluciones arbitrariamente cercanas al óptimo (como una familia de algoritmos de aproximación se llama un esquema de aproximación polinomial-time o PTAS). Otros son imposibles de aproximar dentro de cualquier factor constante, o incluso polinomio, a menos que P = NP, como en el caso del problema máximo de la camarilla. Por lo tanto, un beneficio importante de estudiar algoritmos de aproximación es una clasificación fina de la dificultad de varios problemas duros NP más allá de los que ofrece la teoría de la completa NP. En otras palabras, aunque los problemas completos de NP pueden ser equivalentes (bajo reducciones de tiempo polinomio) entre sí desde la perspectiva de soluciones exactas, los problemas de optimización correspondientes se comportan de forma muy diferente desde la perspectiva de soluciones aproximadas.

Técnicas de diseño de algoritmos

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

algoritmo de salud
Búsqueda local
Enumeración y programación dinámica (que también se utiliza a menudo para aproximaciones parametizadas)
Resolver una relajación de programación convexa para conseguir una solución fraccional. A continuación, convertir esta solución fraccional en una solución viable por algún redondeo apropiado. Las relajacións populares incluyen lo siguiente.
- Relajaciones lineales de programación
- Relajaciones de programación semidefinita
Métodos primario-dual
Ajuste dual
Insertar el problema en alguna métrica y resolver el problema en la métrica. Esto también se conoce como incrustación métrica.
El muestreo aleatorio y el uso de 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 demuestra la inexistencia de algoritmos eficientes con ciertos ratios de aproximación (condicionados a hipótesis ampliamente aceptadas 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. Sumado al conocimiento de la existencia de Christofides' Algoritmo de aproximación 1.5, esto nos dice que el umbral de aproximación 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 y el famoso teorema PCP, 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, conjuntos independientes y coloración logran la relación de aproximación óptima, suponiendo que P ≠ NP.

Practicidad

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 por sí mismas 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) sólo 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 "fuera de la caja" En aplicaciones prácticas, las ideas y conocimientos detrás del diseño de dichos algoritmos a menudo pueden incorporarse de otras maneras en los 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 ser refinados para ser más prácticos. Un ejemplo es el PTAS inicial para Euclidean TSP por Sanjeev Arora (y de forma independiente por Joseph Mitchell) que tenía un tiempo de funcionamiento prohibitivo ${displaystyle n^{O(1/epsilon)}$ para un ${displaystyle 1+epsilon }$ aproximación. Sin embargo, dentro de un año estas ideas fueron incorporadas en un tiempo casi lineal ${displaystyle O(nlog n)}$ algoritmo para cualquier constante ${displaystyle epsilon }$ .

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 demostrado que el valor/coste, f(x), de la solución aproximada A(x) a 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;\\rhomat hrm {OPT}leq f(x)leqmathrm {OPT}qif} {ccH0}cH0}f}cH00}cH00}cH00}cH00}cH00}cH00}cH00}ccH00}cccH00}cH00}ccccH00}ccH00}cH00}cccH00}ccH00}cH00}ccH00}cH00}cH00cH00}cH00}ccH00}cH00}cH

El factor ρ se denomina garantía de desempeño relativo. Un algoritmo de aproximación tiene una garantía absoluta de rendimiento o un error acotado c, si se ha probado para cada instancia x eso

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

Del mismo modo, la garantía de desempeño, R(x,y), de una solución y a un la 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/coste 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 A se dice que 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 tener una relación de aproximación de r(n).

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

El garantía de rendimiento absoluto ${displaystyle mathrm {} _{A}$ de algún algoritmo de aproximación A, donde x se refiere a un caso de un problema, y donde ${displaystyle R_{A}(x)}$ es la garantía de rendimiento A on x (i.e. ρ for problem instance x) es:

{displaystyle mathrm {} _{A}=inf{rgeq 1mid R_{A}(x)leq r,forall x}.}

Es decir, ${displaystyle mathrm {} _{A}$ es la mayor ligada a la relación de aproximación, r, que se ve sobre todas las posibles instancias del problema. Del mismo modo, ratio de rendimiento asintotico ${displaystyle ¿Qué?$ es:

{displaystyle R_{A}{infty }=inf{rgeq 1mid exists nin mathbb {Z} ^{+},R_{A}(x)leq r,forall x, tolerax habitgeq 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.

Garantías de rendimiento
	r- Aprox	***- Aprox	Rel. error	Rel. error	norma. error rel.	abs. error
max: ${displaystyle f(x)geq}$	${displaystyle r^{-1}mathrm {OPT}$	${displaystyle rho mathrm {OPT}$	${displaystyle (1-c)mathrm {OPT}$	${displaystyle (1-c)mathrm {OPT}$	${displaystyle (1-c)mathrm {OPT} +cmathrm {WORST}$	${displaystyle mathrm {OPT}c}$
min: ${displaystyle f(x)leq}$	${displaystyle rmathrm {OPT}$	${displaystyle rho mathrm {OPT}$	${displaystyle (1+c)mathrm {OPT}$	${displaystyle (1-c)^{-1}mathrm {OPT}$	${displaystyle (1-c)^{-1}mathrm {OPT} +cmathrm {WORST}$	${displaystyle mathrm {OPT} +c}$

Términos de É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 ϵ arbitrario > 0 pero que la relación no se ha mostrado (o no se puede) para ϵ = 0. Un ejemplo de esto es la inaproximabilidad óptima (inexistencia de aproximación) relación de 7/8 + ϵ para instancias MAX-3SAT satisfactorias debido a Johan Håstad. Como se mencionó anteriormente, cuando c = 1, se dice que el problema tiene un esquema de aproximación de tiempo polinomial.

Puede aparecer un término ϵ 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 arbitrario ϵ > 0, se puede elegir un N lo suficientemente grande como para que el término k / OPT < ϵ para cada n ≥ N. Para cada ϵ fijo, instancias de tamaño n < N puede 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.

Contenido relacionado

Más resultados...