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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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