APX - APX

En la teoría de la complejidad computacional , la clase APX (una abreviatura de "aproximable") es el conjunto de problemas de optimización NP que permiten algoritmos de aproximación de tiempo polinómico con una relación de aproximación limitada por una constante (o algoritmos de aproximación de factor constante para abreviar). En términos simples, los problemas de esta clase tienen algoritmos eficientes que pueden encontrar una respuesta dentro de algún factor multiplicativo fijo de la respuesta óptima.

Un algoritmo de aproximación se denomina algoritmo de aproximación para el tamaño de entrada si se puede demostrar que la solución que encuentra el algoritmo es como máximo un factor multiplicativo de veces peor que la solución óptima. Aquí, se llama relación de aproximación . Los problemas en APX son aquellos con algoritmos para los que la razón de aproximación es una constante . La razón de aproximación se establece convencionalmente mayor que 1. En el caso de problemas de minimización, es la puntuación de la solución encontrada dividida por la puntuación de la solución óptima, mientras que para los problemas de maximización ocurre lo contrario. Para problemas de maximización, donde una solución inferior tiene una puntuación menor, a veces se indica como menor que 1; en tales casos, el recíproco de es la relación entre la puntuación de la solución encontrada y la puntuación de la solución óptima. ${\ Displaystyle f (n)}$${\ Displaystyle n}$${\ Displaystyle f (n)}$${\ Displaystyle f (n)}$${\ Displaystyle f (n)}$${\ Displaystyle c}$${\ Displaystyle f (n)}$${\ Displaystyle f (n)}$${\ Displaystyle f (n)}$

Se dice que un problema tiene un esquema de aproximación de tiempo polinomial ( PTAS ) si para cada factor multiplicativo del óptimo peor que 1 hay un algoritmo de tiempo polinomial para resolver el problema dentro de ese factor. A menos que P = NP , existen problemas que están en APX pero sin un PTAS, por lo que la clase de problemas con un PTAS está estrictamente contenida en APX. Uno de esos problemas es el problema del embalaje de contenedores .

Dureza APX y completitud APX

Se dice que un problema es APX-difícil si hay una reducción de PTAS de cada problema en APX a ese problema, y ​​que es APX-completo si el problema es APX-difícil y también en APX. Como consecuencia de P ≠ NP ⇒ PTAS ≠ APX, si se asume P ≠ NP, ningún problema APX-hard tiene PTAS. En la práctica, la reducción de un problema a otro para demostrar la completitud de APX a menudo se realiza utilizando otros esquemas de reducción, como reducciones L , que implican reducciones de PTAS.

Ejemplos de

Uno de los problemas completos de APX más simples es MAX-3SAT-3 , una variación del problema de satisfacibilidad booleano . En este problema, tenemos una fórmula booleana en forma normal conjuntiva donde cada variable aparece como máximo 3 veces, y deseamos saber el número máximo de cláusulas que se pueden satisfacer simultáneamente con una sola asignación de valores verdadero / falso a las variables.

Otros problemas de APX-complete incluyen:

• Máximo conjunto independiente en gráficos de grados acotados (aquí, la relación de aproximación depende del grado máximo del gráfico, pero es constante si el grado máximo es fijo).
• Cobertura mínima de vértice . El complemento de cualquier conjunto independiente máximo debe ser una cobertura de vértice.
• Mínimo conjunto dominante en gráficos de grados acotados.
• El problema del viajante de comercio cuando las distancias en la gráfica satisfacen las condiciones de una métrica . TSP es NPO-completo en el caso general.
• El problema de la reconfiguración del token , a través de la reducción en L de la cubierta del conjunto.

Clases de complejidad relacionadas

PTAS

PTAS ( esquema de aproximación de tiempo polinomial ) consiste en problemas que pueden aproximarse dentro de cualquier factor constante además de 1 en el tiempo que es polinomial para el tamaño de entrada, pero el polinomio depende de dicho factor. Esta clase es un subconjunto de APX.

APX-intermedio

A menos que P = NP , existen problemas en APX que no están ni en PTAS ni en APX completo. Se puede pensar que tales problemas tienen una dureza entre los problemas de PTAS y los problemas de APX-completo, y se pueden llamar APX-intermedio . Se cree que el problema del embalaje del contenedor es APX-intermedio. A pesar de no tener un PTAS conocido, el problema de empaquetado de contenedores tiene varios algoritmos "PTAS asintóticos", que se comportan como un PTAS cuando la solución óptima es grande, por lo que intuitivamente puede ser más fácil que los problemas que son APX-hard.

Otro ejemplo de un problema potencialmente intermedio de APX es la coloración mínima de los bordes .

f (n) -APX

También se puede definir una familia de clases de complejidad -APX, donde -APX contiene problemas con un algoritmo de aproximación de tiempo polinomial con una razón de aproximación. De manera análoga, se pueden definir clases -APX-completas; algunas de estas clases contienen problemas de optimización bien conocidos. Log-APX-completeness y poly-APX-completeness se definen en términos de reducciones de AP en lugar de reducciones de PTAS; esto se debe a que las reducciones de PTAS no son lo suficientemente fuertes para preservar la membresía en Log-APX y Poly-APX, aunque son suficientes para APX. ${\ Displaystyle f (n)}$${\ Displaystyle f (n)}$${\ Displaystyle O (f (n))}$${\ Displaystyle f (n)}$

Log-APX-complete, que consiste en los problemas más difíciles que se pueden aproximar de manera eficiente dentro de un factor logarítmico en el tamaño de entrada, incluye un conjunto mínimo dominante cuando el grado es ilimitado.

Poly-APX-complete, que consiste en los problemas más difíciles que se pueden aproximar eficientemente dentro de un polinomio de factores en el tamaño de entrada, incluye un conjunto independiente máximo en el caso general.

También existen problemas que son exp-APX-complete, donde la relación de aproximación es exponencial en el tamaño de entrada. Esto puede ocurrir cuando la aproximación depende del valor de los números dentro de la instancia del problema; estos números pueden expresarse en espacio logarítmico en su valor, de ahí el factor exponencial.

Ver también

• Reducción de preservación de aproximación
• Clase de complejidad
• Algoritmo de aproximación
• Teoremas de clasificación Max / min CSP / Ones : un conjunto de teoremas que permiten la clasificación mecánica de problemas sobre relaciones booleanas en clases de complejidad de aproximación
• MaxSNP : una subclase estrechamente relacionada

Referencias

• Complejo zoológico : APX
• C. Papadimitriou y M. Yannakakis. Clases de optimización, aproximación y complejidad . Journal of Computer and System Sciences, 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 la Wayback Machine . Un compendio de problemas de optimización de NP Archivado 2007-04-05 en Wayback Machine .