Algoritmo de aproximación

Un algoritmo de aproximación es un algoritmo en la investigación de operaciones que se utiliza para encontrar una solución aproximada a un problema de optimización .

El concepto de algoritmo de aproximación se formalizó en 1972 en un artículo de Garey, Graham y Ullman [1] y más tarde de Johnson [2] . Los algoritmos de aproximación a menudo se asocian con problemas NP-difíciles , ya que apenas existe un algoritmo de solución exacta de tiempo polinomial eficiente para ellos, por lo que tiene sentido tratar de encontrar una solución que esté cerca de la óptima. A diferencia de los algoritmos heurísticos , que brindan soluciones suficientemente buenas en un tiempo aceptable, los algoritmos de aproximación brindan una calidad comprobable de la solución dentro de límites de tiempo predeterminados. Idealmente, la aproximación da una solución que difiere de la óptima por algún pequeño factor (por ejemplo, dentro del 5%). Los algoritmos de aproximación se utilizan cada vez más para resolver problemas para los que se conocen algoritmos exactos que se ejecutan en tiempo polinomial, pero se ejecutan durante mucho tiempo. Un ejemplo típico de un algoritmo de aproximación es el algoritmo para resolver el problema de la cobertura de vértices en la teoría de grafos : encuentre un borde descubierto y agregue ambos vértices a la cobertura de vértices, y así sucesivamente hasta que todos estén cubiertos. Está claro que la cobertura resultante puede ser el doble de la óptima. Esta solución es un algoritmo de aproximación con un coeficiente constante de 2.

Los problemas NP-difíciles varían mucho en su aproximabilidad. Algunos, como el problema de bin-packing , se pueden aproximar por cualquier factor mayor que 1 (esta familia de algoritmos se denomina Esquema de tiempo polinomial aproximado , o PTAS ). Otros problemas no se pueden aproximar con ningún coeficiente constante, o incluso con un coeficiente polinomial (si P ≠ NP ), y entre tales problemas se encuentra el problema de la camarilla máxima .

Los problemas NP-difíciles a menudo se pueden expresar en términos de programación entera y se resuelven exactamente en tiempo exponencial . Muchos algoritmos exponenciales se originan al reducir un problema de números enteros a un problema de programación lineal . [3]

No todos los algoritmos de aproximación son adecuados para resolver problemas prácticos. A menudo utilizan CPU / LP / tareas semidefinidas , estructuras de datos complejas o técnicas de programación sofisticadas como subtareas , lo que genera complejidad en la implementación. Algunos algoritmos de aproximación tienen tiempos de ejecución inaceptables aunque el tiempo sea polinomial (por ejemplo, O( n 2000 )). Sin embargo, el estudio de algoritmos tan poco realistas no persigue objetivos puramente teóricos, ya que permite comprender la esencia del problema. Un ejemplo clásico es el algoritmo PTAS inicial para el problema métrico del viajante de comercio , propiedad de Sanjiv Arora , que tenía un tiempo de ejecución casi irreal. Sin embargo, en un año, Arora refinó la idea en un algoritmo que se ejecutaba en tiempo lineal. Dichos algoritmos también son adecuados para tareas en las que el tiempo de ejecución y el costo pueden justificarse. Estas tareas incluyen biología computacional , ingeniería financiera , planificación de transporte y gestión de inventario .

Otra limitación es que el enfoque es adecuado solo para problemas de optimización, pero no para problemas de reconocimiento "puro" como el problema de satisfacibilidad de fórmulas booleanas , aunque a menudo sucede que el método es bastante aplicable para resolver versiones de optimización de los mismos problemas, por ejemplo. ejemplo, para el problema de máxima satisfacibilidad fórmulas booleanas (Max SAT).

La imposibilidad de aproximación ha sido un fructífero campo de investigación en el campo de la complejidad computacional desde que Feige, Goldwasser, Lovasz, Safra y Szegedy establecieron en 1990 que no se puede aproximar el problema de encontrar el máximo conjunto independiente de vértices . Un año después de que Arora demostrara el teorema PCP , los algoritmos de aproximación de Johnson de 1974 para el Problema de Satisfacción Booleano , el Problema de Cobertura de Conjuntos , el Problema de Conjuntos Independientes y el Problema de Número Cromático Gráfico tienen un factor de aproximación óptimo (suponiendo que P ≠ NP)

Eficiencia Garantizada

Para algunos algoritmos de aproximación, es posible probar algunas propiedades del resultado de la aproximación. Por ejemplo, un algoritmo de aproximación ρ A es, por definición, un algoritmo para el cual la relación f ( x ) = valor/costo para resolver el problema de aproximación A ( x ) para el problema x no excede (o no menos, dependiendo de la situación) el producto del coeficiente ρ al valor óptimo [4] [5] :

{\begin{casos}\mathrm {OPT} \leqslant f(x)\leqslant \rho \mathrm {OPT} ,\rho >1;\\\rho \mathrm {OPT} \leqslant f(x) \leqslant \mathrm {OPT} ,\rho <1.\end{casos}}

El coeficiente ρ se denomina eficiencia relativa garantizada .

Un algoritmo de aproximación tiene una eficiencia absoluta garantizada o un error acotado c si para cualquier problema x ,

(\mathrm {OPT} -c)\leqslant f(x)\leqslant (\mathrm {OPT} +c).

La eficiencia garantizada , R ( x, y ), de una solución y para el problema x se define de manera similar

R(x,y)=\max \left({\frac {\mathrm {OPT} {f(y)))),{\frac {f(y)}{\mathrm {OPT} } } \derecho),

donde f ( y ) es la relación valor/costo para la solución y del problema x . Está claro que la eficiencia garantizada no es menor que uno y es igual a uno solo en el caso en que y es la solución óptima. Si el algoritmo A garantiza una solución con la máxima eficiencia r ( n ), entonces se dice que A es un algoritmo de aproximación r ( n ) y tiene un factor de aproximación r ( n ) [ 6 ] [ 7] .

Es fácil ver que en el caso del problema de minimización, ambas definiciones de eficiencia garantizada dan el mismo valor, mientras que para el problema de maximización . ${\ estilo de visualización r = \ rho ^ {-1))$

El importante concepto de error relativo asociado con los problemas de optimización se define en la literatura de diferentes maneras: por ejemplo, W. Kann [7] lo define como , y Ausiello et al [6] como . $|\mathrm {OPT} -f(y)|/\mathrm {OPT}$ ${\displaystyle |\mathrm {OPT} -f(y)|/\max\{\mathrm {OPT},f(y)\))$

La eficiencia absoluta garantizada de algún algoritmo de aproximación A se define como ${\ estilo de visualización \ mathrm {P} _ {A}}$

\mathrm {P} _{A}=\inf\{r\geqslant 1\mid R_{A}(x)\leqslant r,\forall x\}.

Aquí x denota una tarea y a es la eficiencia garantizada de A para x . $R_{A}(x)$

Por lo tanto, es el límite superior de la eficiencia garantizada r para todas las tareas posibles. ${\ estilo de visualización \ mathrm {P} _ {A}}$

La eficiencia asintótica se define de manera similar : ${\displaystyle R_{A}^{\infty))$

R_{A}^{\infty }=\inf\{r\geqslant 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leqslant r,\ para todo x,|x|\geqslant n\}.

Eficiencia garantizada: límites inferiores (superiores) para problemas de minimización (maximización) dados diferentes valores

	r -aprox. [6] [7]	ρ -aprox.	se relaciona. error c [7]	se relaciona. c error [6]	normas relación error c [6] [7]	abdominales. error c [6] [7]
máximo: ${\ Displaystyle f (x) \ geqslant}$	$r^{-1}\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {PEOR}$	$\mathrm {OPT}-c$
min: ${\ Displaystyle f (x) \ leqslant}$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {PEOR}$	$\mathrm {OPT} +c$

Técnicas de desarrollo de algoritmos

Actualmente, existen varios enfoques estándar para el desarrollo de un algoritmo de aproximación. Entre ellos:

Algoritmo codicioso .
Búsqueda local .
Enumeración y programación dinámica .
Resolver un problema de programación convexa debilitada con posibilidad de obtener una solución fraccionada. Luego, la solución se convierte en una solución adecuada mediante el redondeo. Los métodos populares de mitigación de problemas son:
1. Reducción a un problema de programación lineal .
2. Reducción al problema de la programación semidefinida .
Definir alguna métrica simple para un problema y resolver el problema con esta métrica.

Miembro de Epsilon

En la literatura, el coeficiente de aproximación para el problema máximo (o mínimo) se escribe como (o ) para algún número en el caso de que existan variantes del algoritmo con un coeficiente de aproximación para cualquiera pero no para . Un ejemplo de tal aproximación es la imposibilidad de alcanzar el coeficiente 7/8 para el problema MAX-3SAT [8] . $c-\epsilon$ $c+\épsilon$ $C$ ${\ estilo de visualización c \ mp \ épsilon}$ ${\ estilo de visualización \ épsilon > 0}$ ${\ estilo de visualización \ épsilon = 0}$

Notas

↑ MRGarey, RL Graham y JD Ullman. Análisis del peor caso de los algoritmos de asignación de memoria. En Proc. Del 4to ACM Symp. Sobre Teoría de la Computación. 143-152, 1972.
↑ DS Johnson. algoritmos de aproximación para problemas combinatorios. Cómputo J. System Sci. 9, 256-278, 1974.
↑ Gomory, Ralph E. (1958), "Resumen de un algoritmo para soluciones enteras de programas lineales", Bulletin of the American Mathematical Society 64 (5): 275-279, doi:10.1090/S0002-9904-1958-10224- cuatro
↑ Dorit S. Hochbaum, editora, Algoritmos de aproximación para problemas NP-Hard, página XV. Editorial PWS
↑ Tjark Vredeveld, Algoritmos experimentales de aproximación combinatoria: Garantía frente a rendimiento, Technische Universiteit Eindhoven, 2002, SBN 90-386-0532-3
↑ 1 2 3 4 5 6 G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela y M. Protasi. Complejidad y Aproximación: Problemas de Optimización Combinatoria y sus Propiedades de Aproximabilidad . — 1999.
↑ 1 2 3 4 5 6 Viggo Kann. Sobre la aproximabilidad de los problemas de optimización NP- completos . — 1992.
↑ Johan Hastad. Algunos resultados óptimos de inaproximabilidad // Revista de la ACM : revista. — 1999.

Literatura

Vazirani, Vijay V.Algoritmos de aproximación . - Berlín: Springer, 2003. - ISBN 3-540-65367-8 .
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 H. 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: bueno, mejor, mejor y más
Williamson, David & Shmoys, David (26 de abril de 2011), El diseño de algoritmos de aproximación , Cambridge University Press , ISBN 978-0521195270

Enlaces

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

En catálogos bibliográficos	BNF : 16603384f TIERRA : 4500954-5 J9U : 987007475469205171 LCCN : sh2009010988