Полностью полиномиальной аппроксимационной схемой (PTAS, Polynomial-time approximation scheme) называется приближенный алгоритм, в котором уровень точности
выступает в качестве нового параметра, и алгоритм находит
-оптимальное решение за время, ограниченное полиномом от
длины входа и величины .
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
