W pełni wielomianowy schemat aproksymacji
Z Wikipedii
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.
Aktualnie znane są zaledwie dwa problemy, dla których istnieje w pełni wielomianowy schemat aproksymacyjny: problem sumy podzbioru oraz problem plecakowy.
[edytuj] Definicja formalna
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.
[edytuj] Złożoność
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(εn2).
