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

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

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

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

Варианты

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

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

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

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

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

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

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

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

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

Членство в 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, DOI : 10.1006 / jcss.1998.1605
  3. ^ Вазирани, Виджай (2001). Алгоритмы аппроксимации . Берлин: Springer. стр.  69 -70. ISBN 3540653678. OCLC  47097680 .
  4. ^ a b Вазирани, Виджай В. (2003). Аппроксимационные алгоритмы . Берлин: Springer. С. 294–295. ISBN 3-540-65367-8.
  5. ^ H. Kellerer и У. Pferschy и Д. Pisinger (2004). Проблемы с рюкзаком . Springer.CS1 maint: использует параметр авторов ( ссылка )
  6. ^ a b Янсен, Томас (1998), «Введение в теорию сложности и аппроксимационные алгоритмы», в Mayr, Ernst W .; Prömel, Hans Jürgen; Штегер, Ангелика (ред.), Лекции по Proof проверке и аппроксимации алгоритмов , Springer, С. 5-28,. DOI : 10.1007 / BFb0053011 , ISBN 9783540642015. См. Обсуждение после определения 1.30 на стр. 20 .

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