Approximation en temps sous-exponentiel

Il existe des études sur les algorithmes d'approximation pour les problèmes NP complets en temps polynomial et les algorithmes exacts en temps exponentiel. Existe-t-il des études sur les algorithmes d'approximation des problèmes NP complets en temps sous-exponentiel de forme où δ 2 ∈ ( 0 , 1 ) ?$2^{n^{\delta_2}}$$\delta_2\in(0,1)$

Je suis particulièrement intéressé par ce que l'on sait des problèmes approximatifs de temps difficile à polynomial tels que le nombre d'indépendance et le nombre de clique en temps sous-exponentiel Notez que ETH interdit uniquement le calcul exact dans un tel laps de temps. Disons que le nombre d'indépendance est sur un graphique avec le nombre de sommets | V | = 2 s ( n ) n pour quelque 0 < r ( n ) < s ( n ) . Est un 2 ( $\alpha(G)=2^{r(n)n}$$|V|=2^{s(n)n}$$0<r(n)<s(n)$ Schéma d'approximation des facteurs δ 1 possible pour le nombre d'indépendance dans le temps 2 | V | δ 2 = 2 2 δ 2 s ( n ) n où0< δ 1 <1et0< δ 2 <1sont des réels positifs fixes?$2^{(r(n)n)^{\delta_1}}$$2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$$0<\delta_1<1$$0<\delta_2<1$

Cela est pour chaque est - il un δ 2 ∈ ( 0 , 1 ) de telle sorte que α ( G ) peut être approchée à l'intérieur de 2 log δ 1 2 ( α ( G ) ) = 2 ( r ( n ) n ) δ 1 facteur dans le temps 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}}$

Chalermsook, Laekhanukit et Nanongkai (2013) sont un article qui donne une réponse à cette question .

Il existe également des travaux connexes dans le contexte de la tractabilité à paramètres fixes tels que Hajiaghayi, Khandekar et Kortsarz (2013) et Chitnis, Hajiaghayi, Kortsarz (2013) . Ces résultats de dureté sont prouvés sous diverses hypothèses telles que l'ETH ou l'existence de PCP très forts.

$FPA$

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

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