Definicja PTAS a FPTAS

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 | Ja | jest wielkością wejściową, chociaż złożoność czasu jest wykładnicza w 1 / ϵ . FPTAS nie może mieć złożoności czasowej, która rośnie wykładniczo o 1 / ϵ, ale złożoności czasowej proporcjonalnej do | Ja | 8 / ϵ 3 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. $1/\epsilon$

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

3. Co rozumie przez: FPTAS jest najsilniejszym możliwym rezultatem, jaki możemy uzyskać dla problemu trudnego dla NP.

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

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

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

2. $1+\epsilon$$(n+1/\epsilon)^3$$\epsilon$$O(n^3)$$n$

3. $\epsilon$$\epsilon$$\epsilon$$n$$\log(1/\epsilon)$$n$$\log(1/\epsilon)$

4. $C>1$$1+\epsilon$$e^{1/\epsilon}$$\epsilon$$\epsilon$$1+1/n^C$$C$

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