Approximation in subexponentieller Zeit

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 ? $2^{n^{\delta_2}}$ $\delta_2\in(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 für einige . Ist eine $\alpha(G)=2^{r(n)n}$ $|V|=2^{s(n)n}$ $0<r(n)<s(n)$ -Faktor-Approximationsschema für die Unabhängigkeitszahl in Zeit wobeiundeinige feste positive Reale sind? $2^{(r(n)n)^{\delta_1}}$ $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$ $0<\delta_1<1$ $0<\delta_2<1$

Das heißt, für jedes gibt es ein so dass innerhalb von angenähert werden kann Faktor in Zeit $\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 ....
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

und hier

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 ....

Es sollte im vorherigen Kommentar

und wir haben

δ_{2}

$\delta_2$

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

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

T ....

Ich glaube ich hatte vorher Tippfehler.

T ....

Ist es jetzt klar?

T ....

Antworten:

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

arxiv.org/pdf/1308.2617v2.pdf sagt: "Für jedes

größer als eine Konstante ist, muss jeder

Approximationsalgorithmus für das maximale unabhängige Mengenproblem in mindestens

Zeit ausgeführt werden entspricht der Obergrenze von

". So kann ein Näherungsverhältnis

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)})$ .

RB
quelle