Аппроксимационный алгоритм

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

${\displaystyle {\begin{cases}\mathrm {OPT} \leqslant f(x)\leqslant \rho \mathrm {OPT} ,\rho >1;\\\rho \mathrm {OPT} \leqslant f(x)\leqslant \mathrm {OPT} ,\rho <1.\end{cases}}}$

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

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

${\displaystyle (\mathrm {OPT} -c)\leqslant f(x)\leqslant (\mathrm {OPT} +c).}$

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

${\displaystyle R(x,y)=\max \left({\frac {\mathrm {OPT} }{f(y)}},{\frac {f(y)}{\mathrm {OPT} }}\right),}$

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

Легко заметить, что в случае задачи минимизации оба определения гарантированной эффективности дают одно значение, в то время как для задачи максимизации ${\displaystyle r=\rho ^{-1}}$.

Важное понятие относительной ошибки, связанной с задачами оптимизации, определяется в литературе по-разному: например, В. Канн[7] определяет её как ${\displaystyle |\mathrm {OPT} -f(y)|/\mathrm {OPT} }$, а Аузиелло и др.[6] как ${\displaystyle |\mathrm {OPT} -f(y)|/\max\{\mathrm {OPT} ,f(y)\}}$.

Абсолютная гарантированная эффективность ${\displaystyle \mathrm {P} _{A}}$ некоторого аппроксимационного алгоритма A определяется как

${\displaystyle \mathrm {P} _{A}=\inf\{r\geqslant 1\mid R_{A}(x)\leqslant r,\forall x\}.}$

Здесь х обозначает задачу, а ${\displaystyle R_{A}(x)}$ — это гарантированная эффективность A для x.

Таким образом, ${\displaystyle \mathrm {P} _{A}}$ — это верхняя граница гарантированной эффективности r для всех возможных задач.

Подобным образом определяется асимптотическая эффективность ${\displaystyle R_{A}^{\infty }}$:

${\displaystyle R_{A}^{\infty }=\inf\{r\geqslant 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leqslant r,\forall x,|x|\geqslant n\}.}$

Гарантированная эффективность: границы снизу (сверху) для задач минимизации (максимизации) при заданных различных величинах

	r-аппрокс.[6][7]	ρ-аппрокс.	относит. ошибка c[7]	относит. ошибка c[6]	норм. относ. ошибка c[6][7]	абс. ошибка c[6][7]
max: ${\displaystyle f(x)\geqslant }$	${\displaystyle r^{-1}\mathrm {OPT} }$	${\displaystyle \rho \mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} +c\mathrm {WORST} }$	${\displaystyle \mathrm {OPT} -c}$
min: ${\displaystyle f(x)\leqslant }$	${\displaystyle r\mathrm {OPT} }$	${\displaystyle \rho \mathrm {OPT} }$	${\displaystyle (1+c)\mathrm {OPT} }$	${\displaystyle (1-c)^{-1}\mathrm {OPT} }$	${\displaystyle (1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST} }$	${\displaystyle \mathrm {OPT} +c}$

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

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

В литературе коэффициент аппроксимации для задачи на максимум (или минимум) записывается как ${\displaystyle c-\epsilon }$ (или ${\displaystyle c+\epsilon }$) для некоторого числа ${\displaystyle c}$ в том случае, когда существуют варианты алгоритма с коэффициентом аппроксимации ${\displaystyle c\mp \epsilon }$ для любого ${\displaystyle \epsilon >0}$, но не для ${\displaystyle \epsilon =0}$. Пример такой аппроксимации — недостижимость коэффициента 7 / 8 для задачи MAX-3SAT[8].

• 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 (англ.)