W pełni wielomianowy schemat aproksymacji
W pełni wielomianowy schemat aproksymacji (ang. Fully polynomial-time approximation scheme, w skrócie FPTAS) 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 względem rozmiaru instancji rozwiązywanego problemu i rośnie wielomianowo w miarę wzrostu żądanej dokładności.
Każdy w pełni wielomianowy schemat aproksymacji jest równocześnie wielomianowym schematem aproksymacji.
Istnieją w pełni wielomianowe schematy aproksymacji dla problemu sumy podzbioru oraz problemu plecakowego.
Definicja formalna[edytuj | edytuj kod]
Algorytm A jest w pełni wielomianowym schematem aproksymacji dla problemu π jeśli spełnione są następujące warunki:
- dla każdego odpowiedniego ε A jest algorytmem ε-aproksymacyjnym dla π,
- złożoność czasowa A jest ograniczona przez wielomian dwóch zmiennych od rozmiaru instancji problemu podanej na wejściu A i 1/ε, tzn. jest O(P(n, 1/ε)) gdzie P jest wielomianem dwóch zmiennych.
Złożoność[edytuj | edytuj kod]
W pełni wielomianowy schemat aproksymacji ma lepszą złożoność od ogólnego przypadku wielomianowego schematu aproksymacji w tym sensie, że w przeciwieństwie do tego ostatniego daje on gwarancję, że poprawa żądanej dokładności wyznaczanego rozwiązania nie będzie okupiona wykładniczym wzrostem złożoności algorytmu.
Przykładem złożoności w pełni wielomianowego schematu aproksymacji jest O((1/ε)3n2).