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

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (обновление данных)
м (1 версия)
(нет различий)

Версия 19:48, 23 октября 2008

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

Например, алгоритм Задача о рюкзаке:PTAS.


Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «Полностью полиномиальная аппроксимационная схема»