Przybliżenie w czasie podwykonawczym

Istnieją badania dotyczące algorytmów aproksymacyjnych dla całkowitych problemów NP w czasie wielomianowym i dokładnych algorytmów w czasie wykładniczym. Czy istnieją badania na temat algorytmów aproksymacyjnych dla kompletnych problemów NP w podwykładniczym czasie formy gdzie ? $2^{n^{\delta_2}}$ $\delta_2\in(0,1)$

Szczególnie interesuje mnie to, co wiadomo o problemach zbliżonych do czasu trudnego do wielomianu, takich jak liczba niezależności i liczba kliknięć w czasie podwykonawczym? Zauważ, że ETH zabrania jedynie dokładnych obliczeń w takich ramach czasowych. Powiedz, że liczba niezależności wynosi na wykresie z liczbą wierzchołków dla niektórych . Jest $\alpha(G)=2^{r(n)n}$ $|V|=2^{s(n)n}$ $0<r(n)<s(n)$ czynnika a przybliżenie schemat możliwe liczby Independence w czasie gdzieito niektóre ustalone dodatnie wartości rzeczywiste? $2^{(r(n)n)^{\delta_1}}$ $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$ $0<\delta_1<1$ $0<\delta_2<1$

To znaczy, że dla każdego istnieje takie, że może być aproksymowane w granicach czynnika w czasie $\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}}$

approximation-algorithms approximation-hardness T ....
źródło

czy rzeczywiście chciałeś poprosić o podliniowy czas działania w niezależnym numerze?

Sasho Nikolov

Nie, czas działania jest sub wykładniczy. W pełni wykładniczy byłby

. Tutaj czas działania ma formę

i tutaj

2^{| V |}

$2^{|V|}$

2^{| V |^{δ_{1}}}

$2^{|V|^{\delta_1}}$

α (G) = 2^{r (n) n} = | V |^{\frac{r (n)}{s (n)}} < | V | = 2^{s (n) n}

$\alpha(G)=2^{r(n)n}=|V|^{\frac{r(n)}{s(n)}}<|V|=2^{s(n)n}$

T ....

Powinno to być

w poprzednim komentarzu i mamy

δ_{2}

$\delta_2$

α (G) < | V | < 2^{| V |^{δ_{2}}} < 2^{| V |}

$\alpha(G)<|V|<2^{|V|^{\delta_2}}<2^{|V|}$

T ....

Myślę, że wcześniej miałem literówki.

T ....

Czy teraz jest jasne?

T ....

Odpowiedzi:

Artykuł, który daje odpowiedź na to pytanie, to Chalermsook, Laekhanukit i Nanongkai (2013) .

Istnieją również powiązane prace w kontekście ustalania ciągłości parametrów, takich jak Hajiaghayi, Khandekar i Kortsarz (2013) oraz Chitnis, Hajiaghayi, Kortsarz (2013) . Te wyniki twardości są potwierdzone przy różnych założeniach, takich jak ETH lub istnienie bardzo silnych PCP.

Igor Shinkar
źródło

arxiv.org/pdf/1308.2617v2.pdf mówi: „Dla dowolnego

większego niż jakaś stała, każdy algorytm aproksymacji

dla problemu maksymalnego zestawu niezależnego musi działać w czasie co najmniej

. To prawie dopasowuje górną granicę

". Tak więc stosunek przybliżenia

można osiągnąć w

r

$r$

r

$r$

2^{n^{1 - ϵ} / r^{1 + ϵ}}

$2^{{n^{1-\epsilon}}/{r^{1+\epsilon}}}$

2^{n / r}

$2^{n/r}$

r = 2^{(s (n) n)^{δ_{1}}}

$r=2^{({s(n)n})^{\delta_1}}$

2^{2^{r (n) n - (s (n) n)^{δ_{1}}}} = 2^{2^{1 - \frac{(s (n) n)^{δ_{1}}}{r (n) n} r (n) n}} = 2^{2^{δ_{2} r (n) n}}

$2^{2^{r(n)n - ({s(n)n})^{\delta_1}}} = 2^{2^{1 - \frac{({s(n)n})^{\delta_1}}{r(n)n}r(n)n}}=2^{2^{\delta_2 r(n)n}}$

δ_{2} > 1 - \frac{(s (n))^{δ_{1}} n^{δ_{1} - 1}}{r (n)}

$\delta_2 >1 - \frac{({s(n)})^{\delta_1}{n}^{\delta_1-1}}{r(n)}$ ?

T....

You have many $FPA$ (fixed parameter approximation) algorithms for which a sublinear parameter translates into subexponential time in the length of the input.

For example, approximating the number of simple paths of length $k$ , for some $k=n^c$ (where $c<1$ ), gives you a running time of:

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

R B
źródło