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

Перейти к навигацииПерейти к поиску

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

Определение

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

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

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

В алгоритмах PTAS показатель степени в оценке сложности может расти катастрофически при убывании ε, например, когда время выполнения O(n(1/ε)!), что делает этот класс алгоритмов малоинтересным с практической точки зрения. Можно определить эффективную приближенную схему полиномиального времени или efficient polynomial-time approximation scheme (EPTAS), для которой время выполнения должно быть O(nc), где константа 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 имеет временную сложность для всякого фиксированного .

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

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

Примечания

  1. ↑ Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
  2. ↑ 1 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.

Ссылки