Jump to content

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

(Перенаправлено с ФПРАС )

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

См. также

[ редактировать ]
  1. ^ Санджив Арора , Схемы полиномиальной аппроксимации для евклидовой TSP и других геометрических задач, Журнал ACM 45 (5) 753–782, 1998.
  2. ^ Перейти обратно: а б Янсен, Томас (1998), «Введение в теорию сложности и алгоритмы аппроксимации», Майр, Эрнст В.; Премель, Ханс Юрген; Стегер, Анжелика (ред.), Лекции по алгоритмам проверки доказательств и аппроксимации , Springer, стр. 5–28, doi : 10.1007/BFb0053011 , ISBN  9783540642015 . См. обсуждение после определения 1.30 на стр. 20 .
  3. ^ Vazirani, Vijay V. (2003). Approximation Algorithms . Berlin: Springer. pp. 294–295. ISBN  3-540-65367-8 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e15aa532a7adb9885558281978339f55__1680411720
URL1:https://arc.ask3.ru/arc/aa/e1/55/e15aa532a7adb9885558281978339f55.html
Заголовок, (Title) документа по адресу, URL1:
Polynomial-time approximation scheme - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)