Схема полиномиальной аппроксимации - Polynomial-time approximation scheme

В Информатика, а схема полиномиальной аппроксимации (PTAS) является разновидностью алгоритм аппроксимации для проблемы оптимизации (чаще всего, NP-жесткий проблемы оптимизации).

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

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

Варианты

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

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

Любые сильно NP-жесткий задача оптимизации с полиномиально ограниченной целевой функцией не может иметь FPTAS, если P = NP.[4] Однако обратное неверно: например, если P не равно NP, рюкзак с двумя ограничениями не является сильно NP-трудным, но не имеет FPTAS, даже когда оптимальная цель полиномиально ограничена.[5]

Если только P = NP, то FPTAS ⊊ PTAS ⊊APX.[6] Следовательно, при таком предположении, проблемы с APX-hard не имеют PTAS.

Другой детерминированный вариант PTAS - это схема квазиполиномиальной аппроксимации или QPTAS. QPTAS имеет временную сложность для каждого фиксированного .

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

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

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

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

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

использованная литература

  1. ^ Санджив Арора, Схемы аппроксимации полиномиального времени для евклидовой TSP и других геометрических задач, Журнал ACM 45 (5) 753–782, 1998.
  2. ^ Arora, S .; Karger, D .; Карпинский, М. (1999), "Схемы полиномиальной аппроксимации времени для плотных примеров NP-трудных задач", Журнал компьютерных и системных наук, 58 (1): 193–210, Дои:10.1006 / jcss.1998.1605
  3. ^ Вазирани, Виджай (2001). Алгоритмы аппроксимации. Берлин: Springer. стр.74 –83. ISBN  3540653678. OCLC  47097680.
  4. ^ а б Вазирани, Виджай В. (2003). Алгоритмы аппроксимации. Берлин: Springer. С. 294–295. ISBN  3-540-65367-8.
  5. ^ Х. Келлерер, У. Пферши и Д. Писингер (2004). Проблемы с рюкзаком. Springer.CS1 maint: использует параметр авторов (ссылка на сайт)
  6. ^ а б Янсен, Томас (1998), "Введение в теорию сложности и аппроксимационные алгоритмы", в Mayr, Ernst W .; Prömel, Hans Jürgen; Стегер, Анжелика (ред.), Лекции по алгоритмам проверки и аппроксимации, Springer, стр. 5–28, Дои:10.1007 / BFb0053011, ISBN  9783540642015. См. Обсуждение после определения 1.30 на п. 20.

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