В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.

Концепция аппроксимационного алгоритма была формализована в 1972-м году в статье Гарей, Грэма и Гльмана ^[1], а позднее Джонсоном.^[2] Аппроксимационные алгоритмы часто связаны с NP-трудными задачами, поскольку для них вряд ли найдётся эффективный алгоритм точного решения за полиномиальное время, так что имеет смысл попробовать найти близкое оптимальному решение. В отличие от эвристических алгоритмов, дающих достаточно хорошие решения за приемлемое время, аппроксимационные алгоритмы обеспечивают доказуемое качество решения в заранее определённых границах времени. В идеале аппроксимация даёт решение, отличающееся от оптимального на некоторый небольшой множитель (например, в пределах 5%). Аппроксимационные алгоритмы всё чаще используются для решения задач, для которых известны точные алгоритмы, работающее за полиномиальное время, но работающие долго. Типичным примером аппроксимационного алгоритма может служить алгоритм решения задачи о вершинном покрытии в теории графов: найти непокрытое ребро и добавить обе его вершины к покрытию вершин, и так продолжать, пока все не будут покрыты. Ясно, что полученное покрытие может оказаться вдвое больше оптимального. Такое решение является аппроксимационным алгоритмом с постоянным коэффициентом 2.

NP-трудные проблемы сильно различаются по возможности аппроксимации. Некоторые, среди которых, например, задача об упаковке в контейнеры, могут быть аппроксимированы с любым коэффициентом, большим 1 (это семейство алгоритмов называют приближенной схемой полиномиального времени, или PTAS). Другие задачи невозможно аппроксимировать ни с каким постоянным коэффициентом, или даже с полиномиальным коэффициентом (если P ≠ NP), и среди таких задач находится задача о максимальной клике.

NP-трудные задачи часто можно выразить в терминах целочисленного программирования и решаются в точности за экспоненциальное время. Многие экспоненциальные алгоритмы берут своё начало из приведения к задаче линейного программирования целочисленной задачи.^[3]

Не все аппроксимационные алгоритмы подходят для решения практических задач. Часто они используют в качестве подзадач ЦП/ЛП/полуопределённые задачи , сложные структуры данных или изощрённую технику программирования, что ведёт к сложности реализаци. Некоторые аппроксимационные алгоритмы имеют неприемлемое время работы, хотя время и полиномиально (например, O(n²⁰⁰⁰)). Всё же изучение даже таких нереальных алгоритмов не преследует чисто теоретические цели, поскольку оно даёт возможность понять суть проблемы. Классический пример – начальный PTAS алгоритм для метрической задачи о коммивояжёре, принадлежащий Санджив Арора и имевший практически нереальное время работы. Однако, в течение года, Арора отточил идею до алгоритма, работающего за линейное время. Такие алгоритмы пригодны также для задач, в которых время работы и цена могут быть оправданы. К таким задачам относятся Вычислительная биология, Финансовая инженерия, Транспортное планирование и Управление запасами.

Другое ограничение связано с тем, что подход годится только для задач оптимизации, но не для "чистых" задач распознавания наподобие задачи выполнимости булевых формул, хотя часто бывает , что метод вполне применим для решения оптимизационных версий тех же задач, например, для задачи максимальной выполнимости булевых формул (Max SAT).

Невозможность аппроксимации является плодотворным полем исследований в области .вычислительной сложности с тех пор, как в 1990 году Фейг (Feige), Голдвассер (Goldwasser), Ловаш (Lovasz), Сафра (Safra) и Шегеди (Szegedy) установили невозможность аппроксимации задачи нахождения максимального независимого множества вершин. Через год после того, как Арора (Arora) доказал теорему PCP, было доказано, что аппроксимационные алгоритмы Джонсона (Johnson) 1974-го года для задачи о выполнимости булевых формул, задачи о покрытии множества, задачи о независимом множестве и задача о хроматическом числе графа все имеют оптимальный аппроксимационный коэффициент ( в предположении, что P ≠ NP)

Гарантированная эффективность

Для некоторых аппроксимационных алгоритмов удаётся доказать некоторые свойства результата аппроксимации. Например, для ρ-аппроксимационного алгоритма A было доказано, что отношение f(x) = значение/цена решения аппроксимационной задачи A(x) для задачи x не превосходит (или не менее, в зависимости от ситуации) произведения коэффициента ρ на оптимальное значение. ^{[4] [5]}

Коэффициент ρ называется относительной гарантированной эффективностью.

Аппроксимационный алгоритм имеет абсолютную гарантированную эффективность или ограниченную ошибку c, если для любой задачи x выполняется

Подобным образом определяется гарантированная эффективность, R(x,y), решения y для задачи x

R(x,y) =

где f(y) – отношение значение/цена решения y для задачи x. Ясно, что гарантированная эффективность не меньше единицы и равна единице только в случае, когда y является оптимальным решением. Если алгоритм A гарантирует решение с максимальной эффективностью r(n), то говорят, что A является r(n)-аппроксимационным алгоритмом и имеет аппроксимационный коеффициент of r(n).^[6][7]

Легко заметить, что в случае задачи минимизации оба определения гарантированной эффективности дают одно значение, в то время как для задачи максимизации .

Абсолютная гарантированная эффективность некоторого аппроксимационного алгоритма A определяется как

Здесь х обозначает задачу, а - это гарантированная эффективность A для x.

Таким образом, - это верхняя граница гарантированной эффектианости r для всех возможных задач.

Подобным образом определяется асимптотическая эффективность :

Техника разработки алгоритмов

На настоящее время существует несколько стандартных подходов к разработке аппроксимациооного алгоритма. Среди них.

1. Жадный алгоритм
2. Локальный поиск
3. Перебор и динамическое программирование
4. Решение ослабленной задачи выпуклого программирования с возможностью получения дробного решения. Затем решение преобразуется в подходящее решение путём округления. Популярными методами ослабления задачи являются.
   1. Сведение к задаче линейного программирования
   2. Сведение к задаче полуопределённого программирования
5. Определение для задачи некоторой простой метрики и решение задачи с этой метрикой.

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

• Анализ доминирования

Ссылки

• Vazirani Vijay V. Approximation Algorithms. — Berlin: Springer, 2003. — ISBN 3-540-65367-8.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 35: Approximation Algorithms, pp. 1022–1056.
• Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More
• Williamson, David & Shmoys, David (April 26, 2011), «The Design of Approximation Algorithms», Cambridge University Press, ISBN 978-0521195270 

Внешние ссылки

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.