Clase APX

La clase APX (del inglés "approximable") en la teoría de la complejidad computacional  es una clase de problemas NP-difíciles para los cuales existen algoritmos de aproximación de complejidad polinomial con un coeficiente de aproximación constante. En términos más simples, los problemas de esta clase tienen algoritmos eficientes que encuentran soluciones que son peores que las óptimas por no más de un porcentaje fijo. Por ejemplo, existe un algoritmo de complejidad polinomial para resolver el problema de empaquetamiento de contenedores que utiliza no más del 5 % más de contenedores que la cantidad mínima de contenedores necesaria.

Un algoritmo de aproximación se denomina algoritmo de aproximación c con alguna constante c si se puede demostrar que la solución obtenida usando este algoritmo no es más de c veces peor que la solución óptima [1] .

La constante c se llama factor de aproximación . Dependiendo de si el problema es de maximización o de minimización, la solución puede ser c veces mayor o c veces menor que la óptima.

Por ejemplo, tanto el problema de la cobertura de vértices como el problema del vendedor ambulante con la desigualdad del triángulo tienen algoritmos simples para los cuales c = 2 [2] . Por otro lado, se ha demostrado que el problema del viajante de comercio con longitudes de aristas arbitrarias (que no necesariamente satisfacen la desigualdad del triángulo) no se puede aproximar con un coeficiente constante, ya que el problema de encontrar un camino hamiltoniano no se puede resolver en tiempo polinomial (en caso P ≠ NP ) [3] .

Si existe un algoritmo para resolver un problema en tiempo polinomial para cualquier coeficiente fijo mayor que uno (un algoritmo para cualquier coeficiente), se dice que el problema tiene un esquema de aproximación en tiempo polinomial ( PTAS ) . Si P ≠ NP, se puede demostrar que hay problemas que están en la clase APX pero no en PTAS , es decir, problemas que se pueden aproximar por algún factor, pero no por cualquier factor.

Un problema se llama APX -difícil si cualquier problema de la clase APX puede reducirse a este problema, y ​​APX -completo si el problema es APX -difícil y pertenece a la clase APX [1] . La desigualdad P ≠ NP implica que PTAS ≠ APX , P ≠ NP y, por lo tanto, ningún problema difícil de APX pertenece a PTAS .

Si el problema es APX -hard, esto suele ser malo, ya que para P ≠ NP significa que no hay PTAS -algoritmo, que es el tipo de algoritmo de aproximación más útil. Uno de los problemas completos APX más simples es el problema de satisfacibilidad máxima para fórmulas booleanas , una variante del problema de satisfacibilidad de fórmula booleana . En este problema, tenemos una fórmula booleana en forma normal conjuntiva , y queremos obtener el máximo número de subexpresiones que se ejecutarán con una sola sustitución de valores verdadero/falso en las variables. A pesar de que lo más probable es que el problema no pertenezca a PTAS , el valor correcto se puede obtener con una precisión del 30%, y algunas versiones simplificadas del problema tienen PTAS [4] [5] [6] .

Ejemplos

• Algoritmo de Christofides

Notas

1. ↑ 1 2 Tjark Vredeveld. Algoritmos de aproximación combinatoria: desempeño garantizado versus experimental. - Technische Universiteit Eindhoven, 2002. - Pág. 4.12. — ISBN 90-386-0532-3 .
2. ↑ por Dorit S. Hochbaum. Algoritmos de aproximación para problemas NP-difíciles. - Editorial PWS, 1995. - P. 94-144. - ISBN 0-534-94968-1 .
3. ↑ Sanjeev Arora. La aproximabilidad de los problemas NP-difíciles. - Universidad de Princeton.
4. ↑ MICHEL X. GOEMANS, DAVID P. WILLIAMSON. NUEVOS ALGORITMOS DE APROXIMACIÓN 3/4 PARA EL PROBLEMA DE MÁXIMA SATISFIABILIDAD // SIAM J. DISC. MATEMÁTICAS.. - 1994. - V. 7 , núm. 4 . - S. 656-666 .
5. ↑ MICHEL X. GOEMANS, DAVID P. WILLIAMSON. Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad utilizando semidefinido // Diario de la Asociación de Maquinaria Computins. - 1995. - T. 42 , núm. 6 _ - S. 1115-1145 .
6. ↑ Miguel F. Anjos. Enfoques de optimización semidefinida para problemas de satisfacción y máxima satisfacción // Revista sobre satisfacción, modelado booleano y computación. - 2005. - T. 1 . - S. 1-47 .

Enlaces

• C. Papadimitriou y M. Yannakakis. Clases de optimización, aproximación y complejidad. Revista de Ciencias de la Computación y Sistemas, 43:425-440, 1991.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski y Gerhard Woeginger. Máxima satisfacción Archivado el 13 de abril de 2007 en Wayback Machine . Un compendio de problemas de optimización de NP . Archivado el 5 de abril de 2007 en Wayback Machine . Última actualización el 20 de marzo de 2000.