Просмотр исходного текста страницы Полностью полиномиальная аппроксимационная схема

'''Полностью полиномиальной аппроксимационной схемой''' (PTAS, ''Polynomial-time approximation scheme'') называется приближенный алгоритм, в котором уровень точности <m>\varepsilon</m>
выступает в качестве нового параметра, и алгоритм находит
<m>\varepsilon</m>-оптимальное решение за время, ограниченное полиномом от
длины входа и величины <m>\frac{1}{\varepsilon}</m>.

Например, алгоритм [[Задача о рюкзаке:PTAS]].

[[Category:Теория сложности]]
{{replicate-from-custiswiki-to-lib}}