Wielomianowy schemat aproksymacji
Z Wikipedii
Wielomianowy schemat aproksymacji (ang. Polynomial-time approximation scheme, w skrócie PTAS) to 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.
[edytuj] Definicja formalna
Algorytm A jest wielomianowym schematem aproksymacji dla problemu π jeśli spełnione są następujące warunki:
- dla każdego odpowiedniego ε A jest algorytmem ε-aproksymacyjnym dla π,
- dla każdego odpowiedniego ε złożoność czasowa A jest wielomianowa ze względu na rozmiar instancji problemu podanej na wejściu A.
[edytuj] Złożoność
Złożoność czasowa wielomianowego schematu aproksymacji choć wielomianowa względem rozmiaru wejścia dla każdego ustalonego ε, może rosnąć wykładniczo ze zmianą ε. Przykładem takiej złożoności jest 
. Dla każdego ε jest ona wielomianowa, lecz w miarę jak ε maleje złożoność ta rośnie wykładniczo.
