В теории сложности вычислений класс APX (сокращение от «аппроксимируемый») представляет собой набор задач оптимизации NP, которые допускают алгоритмы аппроксимации за полиномиальное время с коэффициентом аппроксимации, ограниченным константой (или, для краткости, алгоритмами аппроксимации с постоянным коэффициентом ). Проще говоря, у задач этого класса есть эффективные алгоритмы, которые могут найти ответ в пределах некоторого фиксированного мультипликативного коэффициента оптимального ответа.
Алгоритм аппроксимации называется -Алгоритм аппроксимации размера ввода если можно доказать, что решение, которое находит алгоритм, является не более чем мультипликативным множителем раза хуже оптимального решения. Здесь,называется коэффициентом аппроксимации . Проблемы в APX - это проблемы с алгоритмами, для которых коэффициент аппроксимации это константа . Коэффициент аппроксимации обычно считается больше 1. В случае задач минимизации- оценка найденного решения, деленная на оценку оптимального решения, в то время как для задач максимизации имеет место обратное. Для задач максимизации, где худшее решение имеет меньшую оценку,иногда указывается как меньше 1; в таких случаях обратная величина - отношение балла найденного решения к баллу оптимального решения.
Говорят, что проблема имеет схему аппроксимации с полиномиальным временем ( 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-полные классы; некоторые такие классы содержат хорошо известные проблемы оптимизации. Полнота лог-APX и поли-APX-полнота определяются в терминах AP-сокращений, а не PTAS-сокращений; это связано с тем, что сокращения PTAS недостаточно сильны, чтобы сохранить членство в Log-APX и Poly-APX, даже если они достаточны для APX.
Log-APX-complete, состоящий из сложнейших задач, которые можно эффективно аппроксимировать с точностью до логарифмического множителя входного размера, включает минимальное доминирующее множество, когда степень не ограничена.
Poly-APX-complete, состоящий из сложнейших задач, которые можно эффективно аппроксимировать с точностью до факторного полинома входного размера, в общем случае включает максимальное независимое множество .
Также существуют проблемы, которые являются exp-APX-complete, где коэффициент аппроксимации экспоненциально зависит от размера ввода. Это может произойти, когда приближение зависит от значения чисел в экземпляре проблемы; эти числа могут быть выражены в пространственном логарифмическом значении, отсюда и экспоненциальный множитель.
Смотрите также
- Приведение с сохранением приближения
- Класс сложности
- Алгоритм приближения
- Макс / мин теоремы классификации CSP / Ones - набор теорем, которые позволяют механически классифицировать проблемы о булевых отношениях в классы сложности аппроксимируемости
- MaxSNP - тесно связанный подкласс
Рекомендации
- Зоопарк сложности : APX
- К. Пападимитриу и М. Яннакакис. Оптимизация, аппроксимация и классы сложности . Журнал компьютерных и системных наук, 43: 425–440, 1991.
- Пьерлуиджи Крещенци, Вигго Канн, Магнус Халльдорссон, Марек Карпински и Герхард Вегингер . Максимальная удовлетворенность [ мертвая ссылка ] . Сборник задач оптимизации NP [ мертвая ссылка ] .