APX - APX

В теории сложности вычислений класс APX (сокращение от «аппроксимируемый») представляет собой набор задач оптимизации NP, которые допускают алгоритмы аппроксимации за полиномиальное время с коэффициентом аппроксимации, ограниченным константой (или, для краткости, алгоритмами аппроксимации с постоянным коэффициентом ). Проще говоря, у задач этого класса есть эффективные алгоритмы, которые могут найти ответ в пределах некоторого фиксированного мультипликативного коэффициента оптимального ответа.

Алгоритм аппроксимации называется алгоритмом -аппроксимации для размера входных данных, если можно доказать, что найденное алгоритмом решение является не более чем мультипликативным множителем, в несколько раз худшим, чем оптимальное решение. Здесь это называется отношением аппроксимации . Проблемы в APX - это проблемы с алгоритмами, для которых коэффициент аппроксимации является постоянным . Коэффициент аппроксимации обычно указывается больше 1. В случае задач минимизации оценка найденного решения делится на оценку оптимального решения, в то время как для задач максимизации имеет место обратное. Для задач максимизации, где худшее решение имеет меньшую оценку, иногда указывается как меньше 1; в таких случаях величина, обратная величине, является отношением балла найденного решения к баллу оптимального решения. ${\ Displaystyle f (п)}$${\ displaystyle n}$${\ Displaystyle f (п)}$${\ Displaystyle f (п)}$${\ Displaystyle f (п)}$${\ displaystyle c}$${\ Displaystyle f (п)}$${\ Displaystyle f (п)}$${\ Displaystyle f (п)}$

Говорят, что проблема имеет схему аппроксимации с полиномиальным временем ( PTAS ), если для каждого мультипликативного коэффициента оптимума хуже 1 существует алгоритм с полиномиальным временем для решения проблемы с точностью до этого коэффициента. Если P = NP, существуют проблемы, которые есть в APX, но без PTAS, поэтому класс проблем с PTAS строго содержится в APX. Одна из таких проблем - проблема упаковки бункера .

APX-твердость и APX-полнота

Проблема называется APX-сложной, если есть сокращение PTAS от каждой проблемы в APX до этой проблемы, и APX-полной, если проблема APX-сложная, а также APX. Как следствие P ≠ NP ⇒ PTAS ≠ APX, если P ≠ NP предполагается, никакая проблема с APX не имеет PTAS. На практике сокращение одной проблемы до другой для демонстрации APX-полноты часто выполняется с использованием других схем сокращения, таких как L-редукции , которые подразумевают сокращение PTAS.

Примеры

Одна из простейших задач APX-complete - MAX-3SAT-3 , вариант логической задачи выполнимости . В этой задаче у нас есть логическая формула в конъюнктивной нормальной форме, где каждая переменная встречается не более 3 раз, и мы хотим знать максимальное количество предложений, которые могут быть одновременно удовлетворены путем однократного присвоения переменных истинных / ложных значений.

Другие проблемы с APX-complete включают:

• Максимальный независимый набор в графах с ограниченными степенями (здесь коэффициент аппроксимации зависит от максимальной степени графа, но является постоянным, если максимальная степень фиксирована).
• Минимальное покрытие вершины . Дополнение любого максимального независимого множества должно быть вершинным покрытием.
• Min доминирующее множество в графах ограниченной степени.
• Задача коммивояжера, когда расстояния в графе удовлетворяют условиям метрики . ТСП в общем случае является НКО-полным .
• Проблема реконфигурации токена через L-редукцию из обложки набора.

Связанные классы сложности

PTAS

PTAS ( схема аппроксимации полиномиального времени ) состоит из задач, которые могут быть аппроксимированы с точностью до любого постоянного множителя, кроме 1, во времени, полиномиального для входного размера, но полином зависит от такого множителя. Этот класс является подмножеством APX.

APX-средний

Если P = NP , в APX существуют проблемы, которые не относятся ни к PTAS, ни к APX-complete. Такие проблемы можно рассматривать как нечто среднее между проблемами PTAS и проблемами APX-complete, и их можно назвать APX-промежуточными . Проблема с упаковкой бункера считается промежуточной APX. Несмотря на отсутствие известного PTAS, задача упаковки бункеров имеет несколько «асимптотических алгоритмов PTAS», которые ведут себя как PTAS, когда оптимальное решение велико, поэтому интуитивно это может быть проще, чем задачи, сложные для APX.

Еще один пример потенциально APX-промежуточной проблемы - минимальная окраска краев .

f (n) -APX

Можно также определить семейство классов сложности -APX, где -APX содержит задачи с полиномиальным алгоритмом аппроксимации времени с коэффициентом аппроксимации. Аналогично можно определить классы -APX-complete; некоторые такие классы содержат хорошо известные проблемы оптимизации. Полнота лог-APX и поли-APX-полнота определяются в терминах AP-сокращений, а не PTAS-сокращений; это связано с тем, что сокращения PTAS недостаточно сильны, чтобы сохранить членство в Log-APX и Poly-APX, даже если они достаточны для APX. ${\ Displaystyle f (п)}$${\ Displaystyle f (п)}$${\ Displaystyle О (е (п))}$${\ Displaystyle f (п)}$

Log-APX-complete, состоящий из сложнейших задач, которые можно эффективно аппроксимировать с точностью до логарифмического множителя входного размера, включает минимальное доминирующее множество, когда степень не ограничена.

Poly-APX-complete, состоящий из сложнейших задач, которые можно эффективно аппроксимировать с точностью до факторного полинома от входного размера, в общем случае включает максимальное независимое множество .

Также существуют проблемы, которые являются exp-APX-complete, где коэффициент аппроксимации экспоненциально зависит от размера ввода. Это может произойти, когда приближение зависит от значения чисел в экземпляре проблемы; эти числа могут быть выражены в пространственном логарифмическом значении, отсюда и экспоненциальный множитель.

Смотрите также

• Приведение с сохранением приближения
• Класс сложности
• Алгоритм приближения
• Макс / мин теоремы классификации CSP / Ones - набор теорем, которые позволяют механически классифицировать проблемы о булевых отношениях в классы сложности аппроксимируемости
• MaxSNP - тесно связанный подкласс

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

• Зоопарк сложности : APX
• К. Пападимитриу и М. Яннакакис. Оптимизация, аппроксимация и классы сложности . Журнал компьютерных и системных наук, 43: 425–440, 1991.
• Пьерлуиджи Крещенци, Вигго Канн, Магнус Халльдорссон, Марек Карпински и Герхард Вёгингер . Максимальное удовлетворение. Архивировано 13 апреля 2007 г. в Wayback Machine . Сборник проблем оптимизации NP. Архивировано 5 апреля 2007 г. в Wayback Machine .