АПХ

Чтобы узнать о других значениях, см. APX (значения) .

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

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

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

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

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

Примеры

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

Другие проблемы, связанные с APX, включают в себя:

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

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

ПТАС

Основная статья: Схема аппроксимации с полиномиальным временем

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

APX-средний уровень

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

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

f(n)-APX

Также можно определить семейство классов сложности $f(n)$-APX, где $f(n)$-APX содержит задачи с алгоритмом аппроксимации полиномиального времени с $O(f(n))$ коэффициент аппроксимации. Аналогично можно определить $f(n)$-APX-полные классы; некоторые такие классы содержат хорошо известные задачи оптимизации. Лог-APX-полнота и поли-APX-полнота определяются с точки зрения AP-сокращения, а не PTAS-сокращения; это связано с тем, что PTAS-сокращения недостаточно сильны, чтобы сохранить членство в Log-APX и Poly-APX, хотя для APX их достаточно.

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

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

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

См. также

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

Ссылки

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