Наближена схемаполіноміального часу
У математиці,наближена схема поліноміального часуабоpolynomial-time approximation scheme(PTAS) позначає клас наближених поліноміальних за часом виконання алгоритмів для вирішення, як правило, NP- важких оптимізаційних завдань. Якщо P = NP, то запровадження цього поняття втрачає сенс. Тому далі припускатимемо, що Р не збігається з NР. І без обмеження спільності визначимо поняття завдання мінімізації.
Зміст
PTAS це сімейство алгоритмів, що залежать від параметра ε, таких, що для довільного набору даних деякої оптимізаційної задачі та параметра ε > 0 алгоритм сімейства за поліноміальний час знаходить рішення з цільовою функцією S [1]
Час виконання PTAS повинен поліноміально залежати відnза будь-якого фіксованого ε, але може довільно змінюватися при зміні ε. Алгоритми з часом виконанняO(n1/ε ) або навітьO(nexp(1/ε) ) є алгоритмами PTAS .
В алгоритмах PTAS показник ступеня в оцінці складності може зростати катастрофічно при зменшенні ε, наприклад, коли час виконання O(n(1/ε)! ), Що робить цей клас алгоритмів малоцікавим з практичної точки зору. Можна визначитиефективну наближену схему поліноміального часуабоefficient polynomial-time approximation scheme(EPTAS), для якої час виконання має бутиO(nc), де константаcне залежить від ε. Це гарантує, що збільшення вхідних даних збільшує час виконання незалежно від величини ε; однак множник під знаком O при цьому продовжує довільно залежати від ε. Подальшим обмеженням більш корисним практично єнаближена схема повністю поліноміального часуабоfullypolynomial-time approximation scheme(FPTAS), яка вимагає, щоб час виконання алгоритму поліноміально залежав і від розміру завданняn, і від 1/ε. Прикладом задачі для якої існує FPTAS є задача ранця. Але для спорідненого завдання про упаковку у контейнери немає навіть PTAS.
Будь-яка NP-важка задача оптимізації з поліноміально обмеженою цільовою функцією не може мати FPTAS. [2] Однак протилежне невірно. Двовимірна задача про ранець не є сильною NP-важкою, але не має FPTAS навіть, коли цільова функція поліноміально обмежена. [3]
Виконується FPTAS ⊊ PTAS ⊊ APX. Отже, APX-важкі завдання немає PTAS.
Іншою модифікацією PTAS єнаближена схема квазі-поліноміального часуабоquasi-polynomial-time approximation scheme(QPTAS). QPTAS має тимчасову складність n p o l y l o g (n) > для будь-якого фіксованого 0>"> ϵ > 0 0> data- > .
Деякі завдання, які не мають PTAS, можуть мати рандомізовані алгоритми з аналогічними властивостями -рандомізовану наближену схему поліноміального часуабоpolynomial-time randomized approximation scheme(PRAS). Алгоритм PRAS з параметром ε > 0 для довільного набору даних оптимізаційної задачі знаходить поліноміальний час рішення, яке з високою ймовірністю не перевищує (1 + ε)OPT. Зазвичай під "високою імовірністю" розуміють можливість більше 3/4, хоча визначення не конкретизує цю величину. Як і алгоритм PTAS, алгоритм PRAS повинен мати час виконання поліноміально залежить відn, але не від 1/ε. За аналогією з детермінованими алгоритмами вводятьсяEPRASподібне до EPTAS іFPRASподібне до FPTAS. [2]