APX

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

Otros problemas que APX-completa puede resolver incluyen:

• Conjunto independiente máximo en grafos de grado limitado (en este caso, la razón de aproximación depende del grado máximo del grafo, pero es constante si el grado máximo es fijo).
• Recubrimiento de vértices mínimo . El complemento de cualquier conjunto independiente maximal debe ser un recubrimiento de vértices.
• Conjunto dominante mínimo en grafos de grado acotado.
• El problema del viajante cuando las distancias en el grafo satisfacen las condiciones de una métrica . El TSP es NPO-completo en el caso general.
• El problema de reconfiguración de tokens , mediante reducción L a partir de la cobertura de conjuntos.

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

A menos que P = NP , existen problemas en APX que no pertenecen ni a PTAS ni son APX-completos. Estos problemas pueden considerarse de dificultad intermedia entre los problemas PTAS y los problemas APX-completos, y se les puede denominar APX-intermedios . Se cree que el problema de empaquetamiento de contenedores es APX-intermedio. A pesar de no tener un PTAS conocido, el problema de empaquetamiento de contenedores cuenta con 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 APX-difíciles.

Otro ejemplo de un problema potencialmente intermedio de APX es el coloreado mínimo de aristas .

También se puede definir una familia de clases de complejidad.${\displaystyle f(n)}$-APX, donde${\displaystyle f(n)}$-APX contiene problemas con un algoritmo de aproximación de tiempo polinomial con un${\displaystyle O(f(n))}$relación de aproximación. Se puede definir análogamente${\displaystyle f(n)}$Clases APX-completas; algunas de estas clases contienen problemas de optimización bien conocidos. La completitud Log-APX y la completitud Poly-APX se definen en términos de reducciones AP en lugar de reducciones PTAS; esto se debe a que las reducciones PTAS no son lo suficientemente fuertes como para preservar la pertenencia a Log-APX y Poly-APX, aunque sí son suficientes para APX.

Log-APX-completo, 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 el conjunto dominante mínimo cuando el grado no está acotado.

Poly-APX-complete, que consiste en los problemas más difíciles que se pueden aproximar de manera eficiente dentro de un factor polinómico en el tamaño de entrada, incluye el conjunto independiente máximo en el caso general.

También existen problemas exp-APX-completos, donde la razón de aproximación es exponencial con respecto al tamaño de la 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 escala logarítmica espacial, de ahí el factor exponencial.