'''Полностью полиномиальной аппроксимационной схемой''' (PTAS, ''Polynomial-time approximation scheme'') называется приближенный алгоритм, в котором уровень точности <math>\varepsilon</math>
+
'''Полностью полиномиальной аппроксимационной схемой''' (PTAS, ''Polynomial-time approximation scheme'') называется приближенный алгоритм, в котором уровень точности <m>\varepsilon</m>
выступает в качестве нового параметра, и алгоритм находит
выступает в качестве нового параметра, и алгоритм находит
−
<math>\varepsilon</math>-оптимальное решение за время, ограниченное полиномом от
+
<m>\varepsilon</m>-оптимальное решение за время, ограниченное полиномом от
−
длины входа и величины <math>\frac{1}{\varepsilon}</math>.
+
длины входа и величины <m>\frac{1}{\varepsilon}</m>.
Например, алгоритм [[Задача о рюкзаке:PTAS]].
Например, алгоритм [[Задача о рюкзаке:PTAS]].
Версия 18:42, 22 октября 2008
Полностью полиномиальной аппроксимационной схемой (PTAS, Polynomial-time approximation scheme) называется приближенный алгоритм, в котором уровень точности
выступает в качестве нового параметра, и алгоритм находит
-оптимальное решение за время, ограниченное полиномом от
длины входа и величины .
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
