Algoritmo de aproximación

En informática e investigación operativa , 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 ampliamente aceptada conjetura P ≠ NP . Según esta conjetura, una amplia clase de problemas de optimización no puede resolverse exactamente en tiempo polinomial . Por lo tanto, el campo de los algoritmos de aproximación intenta comprender cuán cerca es posible aproximar soluciones óptimas a dichos problemas en tiempo polinomial. En la gran mayoría de los casos, la garantía de dichos algoritmos es multiplicativa, expresada como una razón de aproximación o factor de aproximación; es decir, se garantiza que la solución óptima siempre 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 de algoritmo de aproximación con garantía multiplicativa es el algoritmo de Christofides-Serdyukov para el problema del viajante . Proporciona un recorrido del viajante en una métrica de longitud como máximo 3/2 veces la de un recorrido más corto de este tipo. Un ejemplo clásico de algoritmo de aproximación que proporciona una garantía aditiva es la demostración constructiva del teorema de Vizing . Muestra cómo colorear las aristas de un grafo no dirigido con como máximo${\displaystyle \Delta +1}$colores, donde${\displaystyle \Delta }$es el grado máximo de cualquier nodo. Dado que cada arista incidente en un nodo de grado máximo debe tener un color diferente, la demostración constructiva del teorema proporciona un algoritmo de tiempo polinomial que utiliza como máximo un color adicional al mínimo necesario. 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 la planificación en máquinas paralelas no relacionadas.

El diseño y análisis de algoritmos de aproximación implican 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 simulado o los algoritmos genéticos , que encuentran soluciones razonablemente buenas para algunas entradas, pero no proporcionan ninguna indicación clara desde el principio sobre cuándo pueden tener éxito o fracasar.

Existe un gran interés en la informática teórica por comprender mejor los límites de la aproximación a ciertos problemas de optimización famosos. Por ejemplo, una de las preguntas abiertas de larga data 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 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 de lo primero es el algoritmo de Goemans-Williamson para el corte máximo , que resuelve un problema de teoría de grafos utilizando un programa semidefinido proveniente del primer nivel de la jerarquía de suma de cuadrados . ^{[ 4 ]}

Un ejemplo sencillo de algoritmo de aproximación es el del problema de cobertura mínima de vértices , cuyo objetivo es elegir el conjunto más pequeño de vértices tal que cada arista del grafo de entrada contenga al menos un vértice elegido. Una forma de encontrar una cobertura de vértices consiste en repetir el siguiente proceso: encontrar una arista no cubierta, añadir sus dos extremos a la cobertura y eliminar del grafo todas las aristas incidentes a cualquiera de los vértices. Dado que cualquier cobertura de vértices del grafo de entrada debe utilizar un vértice distinto para cubrir cada arista considerada en el proceso (ya que forma un emparejamiento ), la cobertura de vértices resultante es, como máximo, el doble de grande que la óptima. En otras palabras, se trata de un algoritmo de aproximación de factor constante con un factor de aproximación de 2. Según la reciente conjetura de juegos únicos , este factor es incluso el mejor posible. ^{[ 5 ]}

Los problemas NP-difíciles varían enormemente en su aproximabilidad; algunos, como el problema de la mochila , pueden aproximarse dentro de un factor multiplicativo.${\displaystyle 1+\epsilon }$, para cualquier fijo${\displaystyle \epsilon >0}$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 polinomial, a menos que P = NP , como en el caso del problema de la máxima camarilla . Por lo tanto, un beneficio importante del estudio de los algoritmos de aproximación es una clasificación detallada de la dificultad de varios problemas NP-difíciles más allá de la que proporciona la teoría de la NP-completitud . En otras palabras, aunque los problemas NP-completos pueden ser equivalentes (bajo reducciones en tiempo polinomial) 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. Entre ellas se incluyen las siguientes:

1. Algoritmo voraz
2. Búsqueda local
3. Enumeración y programación dinámica (que también se utiliza a menudo para aproximaciones parametrizadas ).
4. Técnicas de programación matemática. Esto implica modelar el problema considerado con una formulación de programación matemática apropiada (típicamente una programación convexa ), como la programación lineal , la programación semidefinida , etc., para obtener una relajación de las soluciones del problema. Luego, se aplican técnicas algorítmicas adicionales a estas formulaciones.
   • Métodos basados ​​en redondeo. Esto implica resolver la formulación considerada para obtener una buena solución fraccionaria y luego convertirla en una solución entera. Las técnicas de redondeo típicas incluyen el redondeo por umbral simple, el redondeo aleatorio , el redondeo iterativo , etc.
   • Métodos de ajuste dual. Esto implica interpretar un algoritmo combinatorio previsto (normalmente uno voraz) como el proceso de calcular una solución factible para el programa dual de la formulación considerada.
   • Métodos primales-duales.
5. Consiste en integrar el problema en una métrica y luego resolverlo utilizando dicha métrica. Esto también se conoce como integración métrica.
6. El muestreo aleatorio y el uso de la aleatoriedad en general, en combinación con los métodos mencionados anteriormente.

Si bien los algoritmos de aproximación siempre ofrecen una garantía a priori del peor caso (ya sea aditiva o multiplicativa), en algunos casos también proporcionan una garantía a posteriori que suele ser mucho mejor. Esto suele ocurrir con los algoritmos que funcionan resolviendo una relajación convexa del problema de optimización sobre 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 de vértices óptima, esto da lugar a otro algoritmo de aproximación 2. 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 de vértices óptima).

Los algoritmos de aproximación como área de investigación están estrechamente relacionados con la teoría de la inaproximabilidad y se nutren de ella, donde se demuestra la no existencia de algoritmos eficientes con ciertas razones de aproximación (condicionado a hipótesis ampliamente aceptadas como la conjetura P ≠ NP) mediante reducciones . En el caso del problema del viajante de comercio métrico, el mejor resultado de inaproximabilidad conocido descarta los 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, estos se obtuvieron mediante métodos ad hoc y en aquel entonces no existía una comprensión sistemática. Solo a partir del resultado de Feige, Goldwasser, Lovász, Safra y Szegedy de 1990 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 alcanzan la razó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 la resolución de problemas de programación lineal no triviales o relajaciones semidefinidas (que pueden recurrir al algoritmo del elipsoide ), estructuras de datos complejas o técnicas algorítmicas sofisticadas, lo que conlleva dificultades de implementación o una mejora en el tiempo de ejecución (en comparación con algoritmos exactos) solo con entradas excesivamente grandes. Dejando a un lado los problemas de implementación y tiempo de ejecución, las garantías que ofrecen los algoritmos de aproximación pueden no ser lo suficientemente sólidas como para justificar su uso práctico. A pesar de su incapacidad para ser utilizados directamente en aplicaciones prácticas, las ideas y los conocimientos que sustentan su diseño a menudo pueden incorporarse de otras maneras en algoritmos prácticos. De este modo, el estudio incluso de algoritmos muy costosos no es una tarea puramente teórica, ya que pueden aportar valiosas perspectivas.

En otros casos, incluso si los resultados iniciales son de interés puramente teórico, con el tiempo, gracias a una mejor comprensión, los algoritmos pueden refinarse para volverse más prácticos. Un ejemplo de ello es el PTAS inicial para el TSP euclidiano de Sanjeev Arora (e independientemente por Joseph Mitchell ) que tenía un tiempo de ejecución prohibitivo de${\displaystyle n^{O(1/\epsilon )}}$por un${\displaystyle 1+\epsilon }$aproximación. ^{[ 10 ]} Sin embargo, en el plazo de un año estas ideas se incorporaron a un tiempo casi lineal.${\displaystyle O(n\log n)}$algoritmo para cualquier constante${\displaystyle \epsilon >0}$. ^{[ 11 ]}

Dado un problema de optimización:

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

dónde${\displaystyle \Pi }$es un problema de aproximación,${\displaystyle I}$el conjunto de entradas y${\displaystyle S}$A partir del conjunto de soluciones, podemos definir la función de coste:

${\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${\displaystyle s^{*}}$para un problema de maximización o minimización:

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

Dada una solución factible${\displaystyle s\in S(i)}$, con${\displaystyle s\neq s^{*}}$, querríamos una garantía de la calidad de la solución, que es un rendimiento que debe garantizarse (factor de aproximación).

Específicamente, tener${\displaystyle A_{\Pi }(i)\in S_{i}}$, el algoritmo tiene un factor de aproximación (o razón de aproximación ) de${\displaystyle \rho (n)}$si${\displaystyle \forall i\in I\ st|i|=n}$, tenemos:

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

Se puede demostrar que la aproximación es precisa ( aproximación precisa ) demostrando que existen casos en los que el algoritmo se comporta en el límite de la aproximación, lo que indica la precisión del límite. En este caso, basta con construir una instancia de entrada diseñada para forzar al algoritmo a un escenario de peor caso.

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/costo, f ( x ), de la solución aproximada A ( x ) para una instancia x no será mayor (o menor, según la situación) que un factor ρ veces el valor, OPT, de una solución óptima.

${\displaystyle {\begin{casos}\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{casos}}}$

El factor ρ se denomina garantía de rendimiento relativo . Un algoritmo de aproximación tiene una garantía de rendimiento absoluto o 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 problemas de minimización, las dos garantías diferentes proporcionan el mismo resultado y que para problemas de maximización, una garantía de rendimiento relativo de ρ es equivalente a una garantía de rendimiento de${\displaystyle r=\rho ^{-1}}$En la literatura, ambas definiciones son comunes, pero está claro cuál se utiliza ya que, para problemas de maximización, ρ ≤ 1 mientras que r ≥ 1.

Garantía de rendimiento absoluto${\displaystyle \mathrm {P} _{A}}$de algún algoritmo de aproximación A , donde x se refiere a una instancia de un problema, y ​​donde${\displaystyle R_{A}(x)}$es la garantía de rendimiento de A en x (es decir, ρ para la instancia del problema x ) es:

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

Es decir que${\displaystyle \mathrm {P} _{A}}$es el límite más grande en la razón de aproximación, r , que se observa en todas las instancias posibles del problema. De igual manera, la razón de rendimiento asintótico${\displaystyle R_{A}^{\infty }}$es:

${\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 la relación de rendimiento absoluto , con un límite inferior n en el tamaño de las instancias del problema. Estos dos tipos de relaciones se utilizan porque existen algoritmos en los que la diferencia entre ambas es significativa.

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

• El análisis de dominancia considera las garantías en términos del rango de la solución calculada.
• PTAS : un tipo de algoritmo de aproximación que toma la razó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

• 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-7Capítulo 35: Algoritmos de aproximación, págs.  1022 – 1056.
• Dorit S. Hochbaum , ed. Algoritmos de aproximación para problemas NP-difíciles , PWS Publishing Company, 1997. ISBN 0-534-94968-1Capítulo 9: Diversas nociones de aproximación: 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

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