Relación entre parámetro fijo y algoritmo de aproximación

Los parámetros fijos y la aproximación son enfoques totalmente diferentes para resolver problemas difíciles. Tienen motivaciones diferentes. La aproximación busca un resultado más rápido con una solución aproximada. El parámetro fijo busca una solución exacta con complejidad de tiempo en términos de la función exponencial o alguna de k y la función polinómica de n donde n es el tamaño de entrada yk es el parámetro. Ejemplo .$2^kn^3$

Ahora mi pregunta, ¿hay algún resultado de límite superior o inferior basado en la relación entre el parámetro fijo y los enfoques de aproximación o no tienen ninguna relación? Por ejemplo, para un problema se dice que es W [ i ] difícil para algunos i > 0 no tiene nada que ver con tener un algoritmo de aproximación c o PTAS. por favor proporcione algunas referencias$P$$W[i]$$i>0$

Existen varias conexiones entre la complejidad parametrizada y los algoritmos de aproximación.

Primero, considere la llamada parametrización estándar de un problema. Aquí, el parámetro es lo que optimizaría en la versión de optimización del problema (el tamaño de la cubierta de vértice para el problema de Cubierta de vértice, el ancho de la descomposición del árbol para el problema de Ancho de árbol, etc.). Veamos concretamente la cubierta Vertex. Cualquier kernel con un número lineal de vértices para Vertex Cover implica un algoritmo de aproximación de tiempo polinomial de factor constante: en la solución aproximada, coloque todos los vértices que han sido forzados a la solución por el algoritmo de kernelization y todos los vértices de la instancia kernelized . Por otro lado, los límites inferiores en el factor de aproximación implican límites inferiores en el tamaño de un núcleo. Por ejemplo, bajo la Conjetura de juegos únicos, Khot y Regev (JCSS 2008)descartar algoritmos de aproximación para Vertex Cover con una relación de cualquier , que descarta un núcleo para Vertex Cover con a lo sumo c k vértices, c < 2 , también.$c<2$$ck$$c<2$

EDITAR: La argumentación para el límite inferior del núcleo en el párrafo anterior es muy informal, y que yo sepa, está abierto si se pueden probar tales límites inferiores en el tamaño del núcleo, incluso para Vertex Cover. Como @Falk señala en los comentarios, el argumento es válido para la mayoría (¿todos?) De los núcleos conocidos. Sin embargo, no veo cómo se podría excluir la existencia de algoritmos de kernelization donde una solución factible de la instancia kernelized tiene una relación de aproximación diferente a la solución correspondiente en la instancia inicial.

Luego, está el problema de PTAS versus FPTAS. Si queremos encontrar una solución dentro de desde óptimo, podemos parametrizar por 1 / ϵ . Entonces, un PTAS corresponde a un algoritmo XP en la configuración parametrizada, mientras que un FPTAS corresponde a un algoritmo FPT. Para un límite inferior de aproximación, es posible que no esperemos un EPTAS para cualquier problema cuya parametrización estándar sea W [1] -hard: ejecutar el EPTAS con ϵ = 1 /$(1+\epsilon)$$1/\epsilon$ resolvería el problema exactamente en el tiempo FPT.$\epsilon=1/(k+1)$

Finalmente, un algoritmo de aproximación FPT es un algoritmo con tiempo de ejecución FPT y una relación de aproximación que puede depender del parámetro. Por ejemplo, la parametrización estándar del problema Cliquewidth tiene un algoritmo de aproximación FPT con relación de aproximación (Oum, WG 2005) , mientras que la parametrización estándar del Conjunto de Dominio Independiente no tiene un algoritmo de aproximación FPT con relación de rendimiento g ( k $(2^{3k+2}-1)/k$ $g(k)$ para cualquier función computable , a menos que FPT = W [2] (Downey et al., IWPEC 2006) . Ver (Marx, The Computer Journal 2008)$g$ para una encuesta sobre aproximación FPT.

$FPTAS$$PFPT$

$Q=(I_Q, S_Q, f_Q, opt_Q)$$NP$$Q$$FPTAS$$Q$$PFPT$ .

$PFPT$ se define como:

$NP$$Q$$PFPT$$O(|x|^{O(1)}k^{O(1)})$$|x|$$x$ .

Se proponen otras caracterizaciones para dos clases de aproximación en [2, Teorema 6.5].

Un problema es

• $PTAS$$ptas^{\infty}$$XP^w$

• $FPTAS$$fptas^{\infty}$$PFPT^w$

$(f)ptas^{\infty}$$(XP)PFPT^w$$\frac{1}{\epsilon}$

1. Esquemas de aproximación de tiempo polinómico y complejidad parametrizada . J. Chen y col. / Matemática discreta aplicada 155 (2007) 180-193.
2. Estructura de la aproximación del tiempo polinomial . EJ van Leeuwen y col. Informe técnico UU-CS-2009-034, diciembre de 2009.