Приближённая схема полиномиального времени

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

ОпределениеПравить

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

Время выполнения 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.^[2] Однако обратное неверно. Двумерная задача о ранце не является сильно NP-трудной, но не имеет FPTAS даже, когда целевая функция полиномиально ограничена.^[3]

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

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

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

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

ПримечанияПравить

↑ Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
↑ ¹ ² Vazirani, Vijay V. Approximation Algorithms (неопр.). — Berlin: Springer, 2003. — С. 294—295. — ISBN 3-540-65367-8.
↑ H. Kellerer and U. Pferschy and D. Pisinger. Knapsack Problems (неопр.). — Springer, 2004.

СсылкиПравить

Зоопарк сложностей: 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.

[1] Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.

[vvv-2] ¹ ² Vazirani, Vijay V. Approximation Algorithms (неопр.). — Berlin: Springer, 2003. — С. 294—295. — ISBN 3-540-65367-8.

[3] H. Kellerer and U. Pferschy and D. Pisinger. Knapsack Problems (неопр.). — Springer, 2004.

[1]

[2]

[3]