Approximation in subexponentieller Zeit

15

Es gibt Studien zu Approximationsalgorithmen für NP-Gesamtprobleme in der Polynomzeit und zu exakten Algorithmen in der Exponentialzeit. Gibt es Studien über Approximationsalgorithmen für NP-Gesamtprobleme in subexponentieller Zeit der Form mit ?2nδ2δ2(0,1)

Ich interessiere mich besonders für das, was über schwer zu polynomialer Zeit approximierbare Probleme wie Unabhängigkeitszahl und Cliquenzahl in subexponentieller Zeit bekannt ist? Beachten Sie, dass die ETH in einem solchen Zeitrahmen nur exakte Berechnungen verbietet. Angenommen, die Unabhängigkeitszahl ist in einem Graphen mit der Scheitelpunktzahl | V | = 2 s ( n ) n für einige 0 < r ( n ) < s ( n ) . Ist eine 2 ( rα(G)=2r(n)n|V|=2s(n)n0<r(n)<s(n) -Faktor-Approximationsschema für die Unabhängigkeitszahl in Zeit 2 | möglich V | δ 2 = 2 2 δ 2 s ( n ) n wobei0< δ 1 <1und0< δ 2 <1einige feste positive Reale sind?2(r(n)n)δ12|V|δ2=22δ2s(n)n0<δ1<10<δ2<1

Das heißt, für jedes gibt es ein δ 2( 0 , 1 ), so dass α ( G ) innerhalb von 2 log δ 1 2 ( α ( G ) ) = 2 ( r ( n ) angenähert werden kann ) n ) δ 1 Faktor in Zeit 2 | V | δ 2 = 2δ1(0,1)δ2(0,1)α(G)2log2δ1(α(G))=2(r(n)n)δ1 & le ;2|V|δ2=22δ2s(n)n

T ....
quelle
Wolltest du eigentlich in der unabhängigen Nummer nach sublinearer Laufzeit fragen?
Sasho Nikolov
Nein, die Laufzeit ist subexponentiell. Voll exponentiell wäre . Hier hat die Laufzeit die Form 2 | V | δ 1 und hier α ( 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 ....
Es sollte im vorherigen Kommentar und wir haben α ( G ) < | V | < 2 | V | δ 2 < 2 | V | . δ2α(G)<|V|<2|V|δ2<2|V|
T ....
Ich glaube ich hatte vorher Tippfehler.
T ....
Ist es jetzt klar?
T ....

Antworten:

10

Ein Artikel, der diese Frage beantwortet, ist Chalermsook, Laekhanukit & Nanongkai (2013) .

Es gibt auch verwandte Arbeiten im Kontext von Fixed Parameter Tractability wie Hajiaghayi, Khandekar & Kortsarz (2013) und Chitnis, Hajiaghayi, Kortsarz (2013) . Diese Härteergebnisse sind unter verschiedenen Annahmen wie ETH oder Vorhandensein sehr starker PCPs belegt.

Igor Shinkar
quelle
1
arxiv.org/pdf/1308.2617v2.pdf sagt: "Für jedes größer als eine Konstante ist, muss jeder r- Approximationsalgorithmus für das maximale unabhängige Mengenproblem in mindestens 2 n 1 - ϵ / r 1 + ϵ Zeit ausgeführt werden entspricht der Obergrenze von 2 n / r ". So kann ein Näherungsverhältnis r = 2 ( s ( n ) n ) δ 1 in 2 2 r ( n ) n - erreicht werden.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)).

RB
quelle