Dureza de aproximación - error aditivo

Existe una rica literatura y al menos un libro muy bueno que establece la dureza conocida de los resultados de aproximación para problemas NP-duros en el contexto de error multiplicativo (por ejemplo, la aproximación 2 para la cobertura de vértices es óptima suponiendo UGC). Esto también incluye clases de complejidad de aproximación bien entendidas como APX, PTAS, etc.

¿Qué se sabe cuando se debe considerar el error aditivo? Una búsqueda en la literatura muestra algunos resultados de tipo de límite superior, especialmente para el empaquetado de contenedores (ver, por ejemplo, http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps ), pero está allí una clasificación de clase de complejidad más completa o hay alguna razón por la cual no es tan interesante o relevante?

Como comentario adicional, por ejemplo, para el embalaje de contenedores, no hay ninguna razón teórica por la que no se pueda encontrar un algoritmo de tiempo polivinílico que siempre esté dentro de una distancia aditiva del óptimo de 1 (aunque estoy en condiciones de ser corregido ) ¿Tal algoritmo colapsaría cualquier clase de complejidad o tendría algún otro efecto teórico significativo?

EDITAR: La frase clave que no utilicé es "clase de aproximación asintótica" (gracias Oleksandr). Parece que hay algo de trabajo en esta área, pero aún no ha alcanzado la misma etapa de madurez que la teoría de las clases clásicas de aproximación.

La pregunta es algo abierta, por lo que no creo que pueda responderse por completo. Esta es una respuesta parcial.

Una observación fácil es que muchos problemas no son interesantes cuando consideramos la aproximación aditiva. Por ejemplo, tradicionalmente la función objetivo del problema Max-3SAT es el número de cláusulas satisfechas. En esta formulación, aproximar Max-3SAT dentro de un error aditivo O (1) es equivalente a resolver Max-3SAT exactamente, simplemente porque la función objetivo se puede escalar copiando la fórmula de entrada muchas veces. La aproximación multiplicativa es mucho más esencial para los problemas de este tipo.

[Editar: En una revisión anterior, había usado el Conjunto independiente como ejemplo en el párrafo anterior, pero lo cambié a Max-3SAT porque el Conjunto independiente no es un buen ejemplo para ilustrar la diferencia entre la aproximación multiplicativa y la aproximación aditiva; El conjunto independiente aproximado incluso dentro de un factor multiplicativo O (1) también es NP-duro. De hecho, Håstad [Has99] muestra una inaplicabilidad mucho más fuerte para el conjunto independiente.]

Pero, como dijiste, la aproximación aditiva es interesante para problemas como el empaquetado de contenedores, donde no podemos escalar la función objetivo. Además, a menudo podemos reformular un problema para que la aproximación aditiva se vuelva interesante.

Por ejemplo, si la función objetivo de Max-3SAT se redefine como la relación entre el número de cláusulas satisfechas y el número total de cláusulas (como a veces se hace), la aproximación aditiva se vuelve interesante. En esta configuración, la aproximación aditiva no es más difícil que la aproximación multiplicativa en el sentido de que la aproximabilidad dentro de un factor multiplicativo 1− ε (0 < ε <1) implica aproximabilidad dentro de un error aditivo ε , porque el valor óptimo es siempre como máximo 1.

Un hecho interesante (que desafortunadamente parece pasarse por alto a menudo) es que muchos resultados de aproximación demuestran la integridad de NP de ciertos problemas de brechaque no se desprende de la mera dureza NP de la aproximación multiplicativa (ver también Petrank [Pet94] y Goldreich [Gol05, Sección 3]). Continuando con el ejemplo de Max-3SAT, es un resultado bien conocido por Håstad [Has01] que es NP-difícil aproximar Max-3SAT dentro de un factor multiplicativo constante mejor que 7/8. Este resultado por sí solo no parece implicar que es NP-difícil aproximar la versión de relación de Max-3SAT dentro de un error aditivo constante más allá de algún umbral. Sin embargo, lo que Håstad [Has01] demuestra es más fuerte que la mera inaplicabilidad multiplicativa: demuestra que el siguiente problema de promesa es NP completo para cada constante 7/8 < s <1:

Gap-3SAT _s
Instancia : fórmula φ A CNF donde cada cláusula implica exactamente tres distintas variables.
Sí, lo prometo : φ es satisfactoria.
Sin promesa : ninguna asignación de verdad satisface más que la fracción s de las cláusulas de φ.

A partir de esto, podemos concluir que es NP-difícil aproximar la versión de relación de Max-3SAT dentro de un error aditivo mejor que 1/8. Por otro lado, la asignación aleatoria simple habitual da aproximación dentro de un error aditivo 1/8. Por lo tanto, el resultado de Håstad [Has01] no solo proporciona la inaplicabilidad multiplicativa óptima para este problema, sino también la inaproximabilidad aditiva óptima. Supongo que hay muchos resultados aditivos de aproximación como esta que no aparecen explícitamente en la literatura.

Referencias

[Gol05] Oded Goldreich. Sobre problemas prometedores (una encuesta en memoria de Shimon Even [1935-2004]). Coloquio electrónico sobre la complejidad computacional , Informe TR05-018, febrero de 2005. http://eccc.hpi-web.de/report/2005/018/

[Has99] Johan Håstad. La camarilla es difícil de aproximar dentro de n ^{1− ε} . Acta Mathematica , 182 (1): 105–142, marzo de 1999. http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Johan Håstad. Algunos resultados óptimos de inaproximabilidad. Journal of the ACM , 48 (4): 798–859, julio de 2001. http://doi.acm.org/10.1145/502090.502098

[Pet94] Erez Petrank. La dureza de la aproximación: ubicación de la brecha. Complejidad computacional , 4 (2): 133–157, abril de 1994. http://dx.doi.org/10.1007/BF01202286

Esta es una respuesta parcial

$ABS$$ABS$

$NP$

-Cada gráfico cúbico es borde 4-colorable en tiempo polinómico pero borde 3-coloreado es NP-duro.

$ABS$$P=NP$

Existe un trabajo reciente sobre las clases de aproximación asintótica y su comparación con las contrapartes clásicas.

Erik Jan van Leeuwen y Jan van Leeuwen. Estructura de la aproximación de tiempo polinomial . Informe técnico UU-CS-2009-034. Diciembre de 2009.