Приближённая схема полиномиального времени (HjnQln'~uugx v]ybg hklnukbngl,ukik fjybyun)

В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации.

Определение

PTAS это семейство алгоритмов, зависящих от параметра ε , таких, что для произвольного набора данных некоторой оптимизационной задачи и параметра ε > 0 алгоритм семейства за полиномиальное время находит решение с целевой функцией S < (1 + ε)OPT, где OPT минимум целевой функции. Например, для задачи коммивояжёра в евклидовом пространстве существует PTAS, которое находит путь обхода длины не более (1 + ε)L, где L длина кратчайшего пути.

Время выполнения PTAS должно полиномиально зависеть от n при любом фиксированном ε, но может произвольно меняться при изменении ε. Алгоритмы со временем выполнения O(n^1/ε) или даже O(n^exp(1/ε)) являются алгоритмами PTAS.

Детерминированные алгоритмы

В алгоритмах PTAS показатель степени в оценке сложности может расти катастрофически при убывании ε, например, когда время выполнения O(n^(1/ε)!), что делает этот класс алгоритмов малоинтересным с практической точки зрения. Можно определить эффективную приближенную схему полиномиального времени или efficient polynomial-time approximation scheme (EPTAS), для которой время выполнения должно быть O(n^c), где константа c не зависит от ε. Это гарантирует, что увеличение размера входных данных увеличивает время выполнения независимо от величины ε; однако множитель под знаком O при этом продолжает произвольно зависеть от ε. Дальнейшим ограничением более полезным на практике является приближенная схема полностью полиномиального времени или fully polynomial-time approximation scheme (FPTAS), которая требует, чтобы время выполнения алгоритма полиномиально зависело и от размера задачи n, и от 1/ε. Примером задачи для которой существует FPTAS является задача о ранце. Но для родственной задачи об упаковке в контейнеры нет даже PTAS.

Всякая сильно NP-трудная задача оптимизации с полиномиально ограниченной целевой функцией не может иметь FPTAS. Однако обратное неверно. Двумерная задача о ранце не является сильно NP-трудной, но не имеет FPTAS даже, когда целевая функция полиномиально ограничена.

Выполняется FPTAS ⊊ PTAS ⊊ APX. Следовательно, APX-трудные задачи не имеют PTAS.

Другой модификацией PTAS является приближенная схема квази-полиномиального времени или quasi-polynomial-time approximation scheme (QPTAS). QPTAS имеет временную сложность $n^{polylog(n)}$ для всякого фиксированного $\epsilon >0$.

Рандомизированные алгоритмы

Некоторые задачи, которые не имеют PTAS могут иметь рандомизированные алгоритмы с аналогичными свойствами - рандомизированную приближенную схему полиномиального времени или polynomial-time randomized approximation scheme (PRAS). Алгоритм PRAS c параметром ε > 0 для произвольного набора данных оптимизационной задачи находит за полиномиальное время решение, которое с высокой вероятностью не превосходит (1 + ε)OPT. Обычно под "высокой вероятностью" понимают вероятность больше 3/4, хотя определение не конкретизирует эту величину. Как и алгоритм PTAS алгоритм PRAS должен иметь время выполнения полиномиально зависящее от n, но не от 1/ε. По аналогии с детерминированными алгоритмами вводятся EPRAS подобное EPTAS и FPRAS подобное FPTAS.

Ссылки

• Зоопарк сложностей: PTAS, EPTAS, FPTAS
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems Архивная копия от 2 октября 2013 на Wayback Machine – list which NP optimization problems have PTAS.