Wielomianowy schemat aproksymacji

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do 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 . Dla każdego ε jest ona wielomianowa, lecz w miarę jak ε maleje złożoność ta rośnie wykładniczo.

Zobacz też[edytuj | edytuj kod]