Aproximação no tempo subexponencial

15

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 2nδ2 onde δ2(0,1) ?

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α(G)=2r(n)n|V|=2s(n)n0<r(n)<s(n) 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?2(r(n)n)δ12|V|δ2=22δ2s(n)n0<δ1<10<δ2<1

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δ1(0,1)δ2(0,1)α(G)2log2δ1(α(G))=2(r(n)n)δ1 ?2|V|δ2=22δ2s(n)n

T ....
fonte
você realmente quis pedir tempo de execução sublinear no número independente?
Sasho Nikolov
Não, o tempo de execução é subexponencial. Totalmente exponencial seria . Aqui o tempo de execução é da forma 2 | V | δ 1 e aqui α2|V|2|V|δ1. α(G)=2r(n)n=|V|r(n)s(n)<|V|=2s(n)n
T ....
δ2α(G)<|V|<2|V|δ2<2|V|
Eu acho que tive erros de digitação antes.
T ....
Está claro agora?
T ....

Respostas:

10

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.

Igor Shinkar
fonte
1
arxiv.org/pdf/1308.2617v2.pdf diz "Para qualquerr maior do que alguma constante, qualquer rO algoritmo de aproximação para o problema máximo do conjunto independente deve ser executado em pelo menos 2n1-ϵ/r1+ϵTempo. Isso quase coincide com o limite superior de2n/r". Então razão de aproximação r=2(s(n)n)δ1 pode ser alcançado em 22r(n)n-(s(n)n)δ1=221-(s(n)n)δ1r(n)nr(n)n=22δ2r(n)n tempo para alguns δ2>1-(s(n))δ1nδ1-1r(n)?
T ....
3

Voce tem muitos FPUMA (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 length k, for some k=nc (where c<1), gives you a running time of:

O((2e)nc2polylog(n)).

R B
fonte