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 $\varepsilon$ A jest algorytmem ε-aproksymacyjnym dla $\pi ,$
• dla każdego odpowiedniego $\varepsilon$ 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 $\varepsilon ,$ może rosnąć wykładniczo ze zmianą $\varepsilon .$ Przykładem takiej złożoności jest $O(n^{\frac {1}{\varepsilon }}).$ Dla każdego $\varepsilon$ jest ona wielomianowa, lecz w miarę jak $\varepsilon$ maleje złożoność ta rośnie wykładniczo.

Zobacz też

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