Existem estudos sobre algoritmos de aproximação para problemas completos de NP em tempo polinomial e algoritmos exatos em tempo exponencial. Existem estudos sobre algoritmos de aproximação para problemas completos de NP no tempo subexponencial da forma onde ?
Estou particularmente interessado no que é conhecido sobre problemas aproximados de tempo difícil a polinomial, como número de Independência e número de Clique em tempo subexponencial? Observe que o ETH proíbe apenas o cálculo exato nesse período de tempo. Digamos que o número da independência seja em um gráfico com contagem de vértices | V | = 2 s ( n ) n para cerca de 0 < r ( n ) < s ( n ) . É um 2 ( r factor-a aproximação esquema possível para o número Independência em vez de 2 | V | δ 2 = 2 2 δ 2 s ( n ) n onde0< δ 1 <1e0< δ 2 <1são alguns reais positivos fixos?
Isto é, para cada existe um δ 2 ∈ ( 0 , 1 ) tal que α ( G ) possa ser aproximado dentro de 2 log δ 1 2 ( α ( G ) ) = 2 ( r ( n ) n ) δ 1 fator no tempo 2 | V | δ 2 = 2 ?
Respostas:
Um artigo que responde a essa pergunta é Chalermsook, Laekhanukit e Nanongkai (2013) .
Também existem trabalhos relacionados no contexto da rastreabilidade de parâmetros fixos, como Hajiaghayi, Khandekar e Kortsarz (2013) e Chitnis, Hajiaghayi, Kortsarz (2013) . Esses resultados de dureza são comprovados sob várias premissas, como ETH ou existência de PCPs muito fortes.
fonte
Voce tem muitosFPUMA (aproximação de parâmetro fixo) para os quais um parâmetro sublinear se traduz em tempo subexponencial no comprimento da entrada.
For example, approximating the number of simple paths of lengthk , for some k=nc (where c<1 ), gives you a running time of:
fonte