В математике , приближенная схема полиномиального времени или 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.

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

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

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

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

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

Примечания

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

Ссылки

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