Aproximación en tiempo subexponental

Hay estudios sobre algoritmos de aproximación para problemas completos de NP en tiempo polinómico y algoritmos exactos en tiempo exponencial. ¿Existen estudios sobre algoritmos de aproximación para problemas completos de NP en tiempo subexponencial de forma donde δ 2 ∈ ( 0 , 1 ) ?$2^{n^{\delta_2}}$$\delta_2\in(0,1)$

Estoy particularmente interesado en lo que se sabe acerca de los problemas aproximados de tiempo difícil a polinómico, como el número de independencia y el número de camarilla en tiempo subexponencial. Tenga en cuenta que ETH solo prohíbe el cálculo exacto en dicho período de tiempo. Digamos que el número de Independencia es en un gráfico con conteo de vértices | V | = 2 s ( n ) n para algunos 0 < r ( n ) < s ( n ) . Es un 2 ( $\alpha(G)=2^{r(n)n}$$|V|=2^{s(n)n}$$0<r(n)<s(n)$ Esquema de aproximación del factor δ 1 posible para el número de Independencia en el tiempo 2 | V | δ 2 = 2 2 δ 2 s ( n ) n donde0< δ 1 <1y0< δ 2 <1son algunos reales positivos fijos?$2^{(r(n)n)^{\delta_1}}$$2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$$0<\delta_1<1$$0<\delta_2<1$

Es decir, por cada ¿hay un δ 2 ∈ ( 0 , 1 ) tal que α ( G ) pueda aproximarse dentro de 2 log δ 1 2 ( α ( G ) ) = 2 ( r ( n ) n ) δ 1 factor en el tiempo 2 | V | δ 2 = $\delta_1\in(0,1)$$\delta_2\in (0,1)$$\alpha(G)$$2^{\log_2^{\delta_1}(\alpha(G))}=2^{(r(n)n)^{\delta_1}}$ ?$2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$

Un artículo que da respuesta a esta pregunta es Chalermsook, Laekhanukit y Nanongkai (2013) .

También hay trabajos relacionados en el contexto de la Tratabilidad de Parámetros Fijos, como Hajiaghayi, Khandekar y Kortsarz (2013) y Chitnis, Hajiaghayi, Kortsarz (2013) . Estos resultados de dureza se prueban bajo varios supuestos, como ETH o la existencia de PCP muy fuertes.

$FPA$

$k$$k=n^c$$c<1$

$O((2e)^{n^c}\cdot 2^{polylog(n)})$