Definicja PTAS a FPTAS

13

Z tego, co przeczytałem w preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D.

Oto definicja PTAS :

Wielomianowy schemat aproksymacji czasu ( PTAS ) dla problemu jest schematem aproksymacji, którego złożoność czasowa jest wielomianowa w wielkości wejściowej. $X$

oraz definicja FPTAS

W pełni wielomianowy schemat aproksymacji czasu ( FPTAS ) dla problemu jest schematem aproksymacji, którego złożoność czasowa jest wielomianowa w wielkości wejściowej, a także wielomianowa w 1 / . $X$ $\epsilon$

Następnie pisarz mówi:

Dlatego w przypadku PTAS akceptowalne byłoby posiadanie złożoności czasowej proporcjonalnej do gdzie jest wielkością wejściową, chociaż złożoność czasu jest wykładnicza w . FPTAS nie może mieć złożoności czasowej, która rośnie wykładniczo o ale złożoności czasowej proporcjonalnej do byłoby w porządku. Jeśli chodzi o przybliżenie najgorszego przypadku, FPTAS to najsilniejszy możliwy wynik, jaki możemy uzyskać dla problemu trudnego dla NP. $|I|^{1/\epsilon}$ $|I|$ $1/\epsilon$ $1/\epsilon$ $|I|^8/\epsilon^3$

Następnie zasugerował następujący rysunek, aby zilustrować związki między klasami problemów:

Oto moje pytania:

$1/\epsilon$
$(n+1/\epsilon)^3$
Co rozumie przez: FPTAS jest najsilniejszym możliwym rezultatem, jaki możemy uzyskać dla problemu trudnego dla NP.
Podsumowując, chciałbym wiedzieć, co dokładnie oznaczają te pojęcia i jakie są ich odrębne właściwości.

Z góry dziękuję.

— M ama D.
źródło

(n + 1 / ϵ)^{3}

$(n+1/\epsilon)^3$

1

Proszę nie pisać więcej niż jednego pytania w jednym poście. Całkiem możliwe, że zrozumienie odpowiedzi na pierwsze pytanie skłoni resztę do naśladowania. (Imho, twoim problemem jest to, że nie rozumiesz, co znaczy „a także wielomian w 1 / ϵ”.)

— Raphael

n

$n$

(n + 1 / ϵ)^{3}

$(n+1/\epsilon)^3$

n

$n$

@RickyDemer masz rację, popełniłem błąd. Dziękuję Ci.

— M am D

15

Pozwól mi odpowiedzieć na twoje pytania w kolejności:

$n$ $1+\epsilon$ $n$ $1/\epsilon$ $O((n/\epsilon)^C)$ $C \geq 0$ $2^{1/\epsilon}$ $O((n/\epsilon)^C)$ $C$
$O((n/\epsilon)^C)$ $O(n^C e^{D/\epsilon})$ $\epsilon$ $E$ $1+1/n^E$
$1+\epsilon$ $(n+1/\epsilon)^3$ $\epsilon$ $O(n^3)$ $n$
$\epsilon$ $\epsilon$ $\epsilon$ $n$ $\log(1/\epsilon)$ $n$ $\log(1/\epsilon)$
$C>1$ $1+\epsilon$ $e^{1/\epsilon}$ $\epsilon$ $\epsilon$ $1+1/n^C$ $C$

— Yuval Filmus
źródło

Nie zachęcaj do niepożądanych działań związanych z publikowaniem postów.

— Raphael

1

$|I|=n$ $\epsilon$ $n^{1/\epsilon}$ $n$ $\epsilon$ $\epsilon$ $1/\epsilon$ $n$ $\mathrm{poly}(n,1/\epsilon)$ $n^4 (1/\epsilon)^3 + (1/\epsilon)^8$ $n^{1/\epsilon}$ $n$ $1/\epsilon$

— Cyriak Antony
źródło

2

ϵ

$\epsilon$

ϵ

$\epsilon$

ϵ

$\epsilon$

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$