Схема полиномиальной аппроксимации

В информатике (в частности , в алгоритмике ) схема аппроксимации с полиномиальным временем ( PTAS ) — это разновидность алгоритма аппроксимации задач оптимизации (чаще всего NP-трудных задач оптимизации).

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

Время работы PTAS должно быть полиномиальным по размеру задачи для каждого фиксированного ε, но может быть разным для разных ε. Таким образом, алгоритм, работающий за время $O (n 1/е)$ или даже $O (n ехр(1/е))$ считается PTAS.

Варианты

Детерминированный

Практическая проблема с алгоритмами PTAS заключается в том, что показатель полинома может резко увеличиваться при уменьшении ε, например, если время выполнения составляет $O (n (1/е)!)$ . Один из способов решения этой проблемы — определить эффективную схему аппроксимации полиномиального времени или EPTAS , в которой время выполнения должно быть $O (n с)$ для постоянной $c,$ не зависящей от $ε$ . Это гарантирует, что увеличение размера задачи будет иметь одинаковое относительное влияние на время выполнения независимо от того, какое ε используется; однако константа под большим О может по-прежнему зависеть от ε произвольно. Другими словами, EPTAS работает за время FPT , где параметром является ε.

Еще более ограничительной и полезной на практике является схема аппроксимации с полностью полиномиальным временем или FPTAS , которая требует, чтобы алгоритм был полиномиальным как по размеру задачи $n$ , так и $по 1/ε$ .

Если P = NP , то FPTAS ⊊ PTAS ⊊ APX . ^[2] Следовательно, при этом предположении APX-сложные задачи не имеют PTAS.

Другим детерминированным вариантом PTAS является схема аппроксимации квазиполиномиального времени или QPTAS . QPTAS имеет временную сложность $n polylog (n полилог$ для каждого фиксированного $ε > 0$ . Более того, PTAS может работать за время FPT для некоторой параметризации задачи, что приводит к параметризованной схеме аппроксимации .

Рандомизированный

Некоторые задачи, не имеющие PTAS, могут допускать рандомизированный алгоритм с аналогичными свойствами, схему рандомизированной аппроксимации с полиномиальным временем или PRAS . PRAS — это алгоритм, который берет пример задачи оптимизации или подсчета и параметр $ε > 0$ и за полиномиальное время выдает решение, которое с высокой вероятностью находится в пределах коэффициента $ε$ от оптимального. Обычно «высокая вероятность» означает вероятность более 3/4, хотя, как и в случае с большинством вероятностных классов сложности, это определение устойчиво к изменениям этого точного значения (минимальное требование обычно превышает 1/2). Как и PTAS, PRAS должен иметь полиномиальное время работы от $n$ , но не обязательно от $ε$ ; с дополнительными ограничениями на время работы в $ε$ можно определить эффективную схему рандомизированной аппроксимации с полиномиальным временем или EPRAS , аналогичную EPTAS, и схему рандомизированной аппроксимации с полностью полиномиальным временем или FPRAS , аналогичную FPTAS. ^[3]

Как класс сложности

Термин PTAS также может использоваться для обозначения класса задач оптимизации, в которых есть PTAS. PTAS — это подмножество APX , и, если P = NP , это строгое подмножество. ^[2]

Членство в PTAS можно показать с помощью PTAS-редукции , L-редукции или P-редукции , все из которых сохраняют членство в PTAS, и их также можно использовать для демонстрации PTAS-полноты. С другой стороны, продемонстрировать непринадлежность к PTAS (а именно, отсутствие PTAS) можно, показав, что проблема является APX-сложной, после чего существование PTAS покажет P = NP. Твердость APX обычно проявляется через снижение PTAS или снижение AP .

См. также

Параметризованная схема аппроксимации — схема аппроксимации, работающая за FPT . время

Ссылки

^ Санджив Арора , Схемы полиномиальной аппроксимации для евклидовой TSP и других геометрических задач, Журнал ACM 45 (5) 753–782, 1998.
^ Перейти обратно: ^а ^б Янсен, Томас (1998), «Введение в теорию сложности и алгоритмы аппроксимации», Майр, Эрнст В.; Премель, Ханс Юрген; Стегер, Анжелика (ред.), Лекции по алгоритмам проверки доказательств и аппроксимации , Springer, стр. 5–28, doi : 10.1007/BFb0053011 , ISBN 9783540642015 . См. обсуждение после определения 1.30 на стр. 20 .
^ Vazirani, Vijay V. (2003). Approximation Algorithms . Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8 .

Внешние ссылки

Зоопарк сложности: ПТАС , ЕПТАС .
Пьерлуиджи Крещенци, Вигго Канн, Магнус Халлдорссон, Марек Карпински и Герхард Вегингер , Сборник задач оптимизации NP - перечислите, какие задачи оптимизации NP имеют PTAS.

[1] Санджив Арора , Схемы полиномиальной аппроксимации для евклидовой TSP и других геометрических задач, Журнал ACM 45 (5) 753–782, 1998.

[Jansen-2] Перейти обратно: ^а ^б Янсен, Томас (1998), «Введение в теорию сложности и алгоритмы аппроксимации», Майр, Эрнст В.; Премель, Ханс Юрген; Стегер, Анжелика (ред.), Лекции по алгоритмам проверки доказательств и аппроксимации , Springer, стр. 5–28, doi : 10.1007/BFb0053011 , ISBN 9783540642015 . См. обсуждение после определения 1.30 на стр. 20 .

[vvv-3] Vazirani, Vijay V. (2003). Approximation Algorithms . Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8 .

[1]

[2]

[3]