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