АПХ

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

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

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

Говорят, что проблема является 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-комплектом, включают в себя:

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

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

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

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

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

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

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

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

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

• Зоопарк сложности : APX
• C. Papadimitriou и M. Yannakakis. Оптимизация, аппроксимация и классы сложности. Журнал компьютерных и системных наук, 43:425–440, 1991.
• Пьерлуиджи Крешенци, Вигго Канн, Магнус Халлдорссон, Марек Карпински и Герхард Вёгингер . Максимальная выполнимость Архивировано 13.04.2007 на Wayback Machine . Сборник задач оптимизации NP Архивировано 05.04.2007 на Wayback Machine .