Wielomianowy schemat aproksymacji

Wielomianowy schemat aproksymacji (ang. Polynomial-Time Approximation Scheme, w skrócie PTAS) – algorytm aproksymacyjny, który pozwala na uzyskanie dowolnie dobrego rozwiązania przybliżonego danego problemu optymalizacyjnego i którego złożoność czasowa jest wielomianowa dla każdej żądanej dokładności.

Definicja formalna

Algorytm A jest wielomianowym schematem aproksymacji dla problemu $\pi$ jeśli spełnione są następujące warunki:

• dla każdego odpowiedniego $\epsilon$ A jest algorytmem ε-aproksymacyjnym dla $\pi ,$
• dla każdego odpowiedniego $\epsilon$ złożoność czasowa A jest wielomianowa ze względu na rozmiar instancji problemu podanej na wejściu A.

Złożoność

Złożoność czasowa wielomianowego schematu aproksymacji choć wielomianowa względem rozmiaru wejścia dla każdego ustalonego $\epsilon ,$ może rosnąć wykładniczo ze zmianą $\epsilon .$ Przykładem takiej złożoności jest $O(n^{\frac{1}{\epsilon }}).$ Dla każdego $\epsilon$ jest ona wielomianowa, lecz w miarę jak $\epsilon$ maleje złożoność ta rośnie wykładniczo.

Zobacz też

• W pełni wielomianowy schemat aproksymacji
• L-redukcja