Przybliżenie w czasie podwykonawczym

15

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( 0 , 1 ) ?2nδ2δ2(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 | V | = 2 s ( n ) n dla niektórych 0 < r ( n ) < s ( n ) . Jest 2 ( rα(G)=2r(n)n|V|=2s(n)n0<r(n)<s(n) czynnika a przybliżenie schemat możliwe liczby Independence w czasie 2 | V | δ 2 = 2 2 δ 2 s ( n ) n gdzie0< δ 1 <1i0< δ 2 <1to niektóre ustalone dodatnie wartości rzeczywiste?2(r(n)n)δ12|V|δ2=22δ2s(n)n0<δ1<10<δ2<1

To znaczy, że dla każdego istnieje δ 2( 0 , 1 ) takie, że α ( G ) może być aproksymowane w granicach 2 log δ 1 2 ( α ( G ) ) = 2 ( r ( n ) n ) hemibursztynianu 1 czynnika w czasie 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 ....
ź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ę 2 | V | δ 1 i tutaj α ( G ) = 2 r ( n ) n = | V | r ( n )2|V|2|V|δ1. α(G)=2r(n)n=|V|r(n)s(n)<|V|=2s(n)n
T ....
Powinno to być w poprzednim komentarzu i mamy α ( G ) < | V | < 2 | V | δ 2 < 2 | V | . δ2)α(sol)<|V.|<2)|V.|δ2)<2)|V.|
T ....
Myślę, że wcześniej miałem literówki.
T ....
Czy teraz jest jasne?
T ....

Odpowiedzi:

10

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
1
arxiv.org/pdf/1308.2617v2.pdf mówi: „Dla dowolnego większego niż jakaś stała, każdy algorytm aproksymacji r dla problemu maksymalnego zestawu niezależnego musi działać w czasie co najmniej 2 n 1 - ϵ / r 1 + ϵ . To prawie dopasowuje górną granicę 2 n / r ". Tak więc stosunek przybliżenia r = 2 ( s ( n ) n ) δ 1 można osiągnąć w 2 2 r ( n ) n -rr2n1ϵ/r1+ϵ2n/rr=2(s(n)n)δ122r(n)n(s(n)n)δ1=221(s(n)n)δ1r(n)nr(n)n=22δ2r(n)nδ2>1(s(n))δ1nδ11r(n)?
T....
3

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=nc (where c<1), gives you a running time of:

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

R B
źródło