Wielomianowy schemat aproksymacji

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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

Złożoność[edytuj | edytuj kod]

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

Zobacz też[edytuj | edytuj kod]