Algoritmos de aproximación de tiempo superpolinomial para problemas de optimización

Esto está motivado por mi pregunta anterior, Algoritmos de aproximación de tiempo súper polinomial para MAX-3SAT . Para muchos problemas de optimización, para cada uno tenemos una aproximación inferior de aproximación inferior asumiendo alguna conjetura teórica de complejidad ampliamente creída. En otras palabras, no existe un algoritmo de tiempo polinómico para tales problemas de optimización con una relación de aproximación mejor que algunos (relación diferente para cada problema).α $\alpha$$\alpha$$\alpha$

¿Existen problemas de optimización para los cuales podemos lograr una relación de aproximación mejor que si permitimos algoritmos de tiempo súper polinomiales? ¿Podemos lograr mejores relaciones de aproximación usando algoritmos de tiempo cuasi-polinomiales ( ) o incluso usando algoritmos de tiempo sub-exponenciales ( )?n O ( log n ) 2 o ( n $\alpha$$n^{O(\log n)}$$2^{o(n)}$

Agradecería una encuesta de tales resultados.

Un ejemplo es el conjunto máximo independiente . Es NP-difícil aproximar el problema con la relación (Zuckerman, 2007) . Sin embargo, Bourgeois et al. (2011) dan un algoritmo de aproximación simple con tiempo de ejecución . Aquí, denota el número de vértices del gráfico de entrada y la notación oculta los factores polinomiales.$n^{1-\epsilon}$ O * ( 2 $n^{1/2}$nO$O^*(2^{\sqrt{n} \log n})$$n$$O^*$

Otro ejemplo es el problema del ancho de banda . Dunagan y Vempala (2001) diseñan un algoritmo con relación de aproximación y tiempo de ejecución . Que yo sepa, la aproximación de tiempo polinomial más conocida tiene una relación de aproximación (Lee, 2009) ; sin embargo, no se conoce el límite inferior para la mejor relación de aproximación alcanzable en el tiempo polinómico.O ( n log n ) O ( log 3 n ( log log n ) 1 / 4 ) ω ( $O(\log^3 n)$$O(n^{\log n})$$O(\log^3 n (\log \log n)^{1/4})$ $\omega(\sqrt{\log n / \log \log n})$