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

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

Материал из CustisWiki

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

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

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