Из Википедии, бесплатной энциклопедии
  (Перенаправлено из FPTAS )
Перейти к навигации Перейти к поиску

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

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

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

Варианты [ править ]

Детерминированный [ править ]

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

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

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

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

Случайное [ править ]

Некоторые задачи, не имеющие PTAS, могут допускать рандомизированный алгоритм с аналогичными свойствами, схему рандомизированной аппроксимации с полиномиальным временем или PRAS . PRAS - это алгоритм, который берет пример задачи оптимизации или подсчета и параметра ε> 0 и за полиномиальное время выдает решение, которое с высокой вероятностью находится в пределах коэффициента ε от оптимального. Обычно «высокая вероятность» означает вероятность больше 3/4, хотя, как и в случае с большинством вероятностных классов сложности, определение устойчиво к вариациям этого точного значения (минимальное требование обычно больше 1/2). Как и PTAS, PRAS должен иметь полиномиальное время работы от n, но не обязательно в ε; с дополнительными ограничениями на время выполнения в ε, можно определить эффективную схему рандомизированной аппроксимации с полиномиальным временем или 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, 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: uses authors parameter (link)
  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 .

Внешние ссылки [ править ]

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