Персональные инструменты
 

Полностью полиномиальная аппроксимационная схема — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
'''Полностью полиномиальной аппроксимационной схемой''' (PTAS, ''Polynomial-time approximation scheme'') называется приближенный алгоритм, в котором уровень точности <math>\varepsilon</math>
+
#REDIRECT [[discopal:{{PAGENAME}}]]
выступает в качестве нового параметра, и алгоритм находит
+
<math>\varepsilon</math>-оптимальное решение за время, ограниченное полиномом от
+
длины входа и величины <math>\frac{1}{\varepsilon}</math>.
+
 
+
Например, алгоритм [[Задача о рюкзаке:PTAS]].
+
 
+
[[Category:Теория сложности]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:31, 13 июня 2011

  1. REDIRECT discopal:Полностью полиномиальная аппроксимационная схема