ТОЧКА ДОСТУПА
-
Определение класса APX
- APX — это класс NP задач оптимизации, решаемых с использованием алгоритмов аппроксимации с постоянным коэффициентом.
- Задачи в APX имеют эффективные алгоритмы, которые находят решение с точностью до фиксированного коэффициента.
-
Алгоритмы аппроксимации
- Алгоритм аппроксимации — это алгоритм, который находит решение, не превышающее мультипликативный коэффициент оптимального решения.
- Коэффициент аппроксимации указывает на отношение найденного решения к оптимальному.
-
Проблемы в APX
- Проблемы в APX связаны с алгоритмами с постоянным коэффициентом аппроксимации.
- Если P = NP, то некоторые проблемы в APX не имеют PTAS, что делает их полными для APX.
-
Примеры задач в APX
- MAX-3SAT-3 — это задача, в которой нужно найти максимальное количество предложений, выполнимых при однократном присвоении значений переменным.
- Другие примеры включают задачи упаковки в мусорные баки, минимальное покрытие вершины и минимальное доминирующее множество в графах.
-
Связанные классы сложности
- PTAS — это класс задач, которые могут быть аппроксимированы с любой точностью за полиномиальное время.
- APX-промежуточные задачи находятся между PTAS и задачами в APX.
- Существуют также классы сложности
- f
- (
- n
- )
- APX, где
- это коэффициент аппроксимации.
-
Дополнительные сведения
- Существуют также задачи, которые являются полными exp-APX, где коэффициент аппроксимации зависит от экспоненциального значения чисел в задаче.
- Для более детального изучения класса APX можно обратиться к литературе, указанной в конце статьи.
Полный текст статьи: