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

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

Например, алгоритм Задача о рюкзаке:PTAS.
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.