Схема полиномиальной аппроксимации
В информатике (в частности , в алгоритмике ) схема аппроксимации с полиномиальным временем ( 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.