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.


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.


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 <math>O(n^{\frac{1}{\epsilon}})</math>. Dla każdego ε jest ona wielomianowa, lecz w miarę jak ε maleje złożoność ta rośnie wykładniczo.


Zobacz również

  • W pełni wielomianowy schemat aproksymacji,
  • L-redukcja.
Tags: ,