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

Для деяких апроксимаційних алгоритмів вдається довести деякі властивості результату апроксимації. Наприклад, ρ-апроксимаційний алгоритм 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	відносна помилка c	норм. відносна помилка c	абс. помилка c
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, Clifford and 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 (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.