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

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

Концепція апроксимаційного алгоритму формалізовано 1972 року в статті Ґарея^[en], Грема і Ульмана^[1], а пізніше Джонсоном^[2].

Апроксимаційні алгоритми часто пов'язані з NP-складними задачами, оскільки для них навряд чи знайдеться ефективний алгоритм точного розв'язування за поліноміальний час, так що є сенс спробувати знайти близький до оптимального розв'язок.

На відміну від евристичних алгоритмів, що дають досить хороші розв'язки за прийнятний час, апроксимаційні алгоритми забезпечують доказову якість розв'язку в заздалегідь визначених межах часу. В ідеалі апроксимація дає розв'язок, що відрізняється від оптимального на деякий невеликий множник (наприклад, у межах 5 %).

Апроксимаційні алгоритми все частіше використовують для розв'язування задач, для яких відомі точні алгоритми, що працюють за поліноміальний час, але працюють довго.

Типовим прикладом апроксимаційного алгоритму є алгоритм розв'язування задачі про вершинне покриття в теорії графів: знайти непокрите ребро і додати обидві його вершини до покриття вершин, і так продовжувати, поки всі не будуть покриті. Ясно, що отримане покриття може виявитися вдвічі більшим від оптимального. Таке розв'язування є апроксимаційним алгоритмом зі сталим коефіцієнтом 2.

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

NP-складні задачі часто можна виразити в термінах цілочисельного програмування та розв'язати точності за експоненційний час. Багато експоненційних алгоритмів беруть свій початок зі зведення до задачі лінійного програмування^[en] цілочисельної задачі.^[3]

Не всі апроксимаційні алгоритми придатні для розв'язування практичних задач. Часто вони використовують як підзадачі ЦП/ЛП/напіввизначені задачі, складні структури даних або витончену техніку програмування, що веде до складності реалізації. Деякі апроксимаційні алгоритми мають неприйнятний час роботи, хоча час і поліноміальний (наприклад, O(n²⁰⁰⁰)). Все ж вивчення навіть таких нереальних алгоритмів має не лише чисто теоретичну мету, оскільки воно дає змогу зрозуміти суть проблеми. Класичний приклад — початковий PTAS-алгоритм для метричної задачі про комівояжера Санджива Арори^[ru], що мав практично нереальний час роботи. Однак, протягом року Арора розвинув ідею до алгоритму, що працює за лінійний час. Такі алгоритми придатні також для задач, у яких час роботи і ціна можуть бути виправданими. До таких задач належать обчислювальна біологія, фінансовий інжиніринг, транспортне планування^[en] і керування запасами^[en].

Інше обмеження пов'язане з тим, що підхід годиться тільки для задач оптимізації, але не для «чистих» задач розпізнавання на зразок задачі здійсненності булевих формул, хоча часто буває, що метод цілком застосовний для розв'язання оптимізаційних версій тих самих задач, наприклад, для задачі максимальної здійсненності булевих формул (Max SAT).

Неможливість апроксимації є плідним полем досліджень в галузі обчислювальної складності відтоді, як у 1990 році Фейг^[en], Голдвассер, Ловас, Сафра^[en] і Шегеді^[en] встановили неможливість апроксимації задачі знаходження максимальної незалежної множини вершин. Через рік після того, як Арора довів теорему PCP, було доведено, що апроксимаційні алгоритми Джонсона 1974 року для задачі про здійсненність булевих формул, задачі про покриття множини, задачі про незалежну множину і задачі про хроматичне число графу мають оптимальний апроксимаційний коефіцієнт (у припущенні, що P ≠ NP)

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

Для деяких апроксимаційних алгоритмів вдається довести деякі властивості результату апроксимації. Наприклад, ρ-апроксимаційний алгоритм A — це за визначенням алгоритм, для якого відношення f(x) = цінність/витрати для розв'язання апроксимаційної задачі A(x) для задачі x не перевищує (або не менше, залежно від ситуації) добутку коефіцієнта ρ на оптимальну величину цінності^[4]^[5]:

{\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 виконується

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

Подібним чином визначається гарантована ефективність, R(x, y), розв'язку y для задачі x

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].

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

Важливе поняття відносної помилки, пов'язаної із завданнями оптимізації, визначається в літературі по-різному: наприклад, В. Канн^[sv]^[7] визначає її як $|\mathrm {OPT} -f(y)|/\mathrm {OPT}$ , а Озіелло та ін^[6] як $|\mathrm {OPT} -f(y)|/\max\{\mathrm {OPT} ,f(y)\}$ .

Абсолютна гарантована ефективність $\mathrm {P} _{A}$ деякого апроксимаційного алгоритму A визначається як

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

Тут х позначає задачу, а $R_{A}(x)$ — це гарантована ефективність A для x.

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

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

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: $f(x)\geqslant$	$r^{-1}\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} -c$
min: $f(x)\leqslant$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} +c$

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

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

Жадібний алгоритм.
Локальний пошук.
Перебір і динамічне програмування.
Розв'язання послабленої задачі опуклого програмування з можливістю отримання дробового розв'язку. Потім розв'язок перетворюється на відповідний розв'язок шляхом округлення. Популярними методами ослаблення задачі є:
1. Зведення до задачі лінійного програмування.
2. Зведення до задачі напіввизначеного програмування.
Визначення задачі для деякої простої метрики і розв'язання задачі з цієї метрикою.

Епсилон-член

У літературі коефіцієнт апроксимації для задачі на максимум (або мінімум) записується як $c-\epsilon$ (або $c+\epsilon$ ) для деякого числа $c$ в тому випадку, коли існують варіанти алгоритму з коефіцієнтом апроксимації $c\mp \epsilon$ для будь-якого $\epsilon >0$ , але не для $\epsilon =0$ . Приклад такої апроксимації — недосяжність коефіцієнта 7 / 8 для задачі MAX-3SAT^[8].

Див. також

Складність апроксимації

Примітки

↑ M.R.Garey, R.L. Graham and J.D. Ullman. Worst case analysis of memory allocation algorithms. In Proc. Of the 4th ACM Symp. On Theory of Computing. 143—152, 1972.
↑ D.S.Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9, 256—278, 1974.
↑ Gomory, Ralph E. (1958), «Outline of an algorithm for integer solutions to linear programs», Bulletin of the American Mathematical Society 64 (5): 275—279, doi:10.1090/S0002-9904-1958-10224-4.
↑ Dorit S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, page XV. PWS Publishing Company
↑ Tjark Vredeveld, Combinatorial approximation algorithms: Guaranteed versus experimental performance, Technische Universiteit Eindhoven, 2002, SBN 90-386-0532-3
↑ ^а ^б ^в G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. — 1999.
↑ ^а ^б ^в Viggo Kann. [1] — 1992. Архівовано з джерела 12 серпня 2021
↑ Johan Håstad. Some Optimal Inapproximability Results // Journal of the ACM : journal. — 1999. — 5 November. Архівовано з джерела 12 березня 2012. Процитовано 16 листопада 2020.

Література

Vazirani, Vijay V.^[en]. 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 [Архівовано 2 жовтня 2013 у Wayback Machine.].

[1] M.R.Garey, R.L. Graham and J.D. Ullman. Worst case analysis of memory allocation algorithms. In Proc. Of the 4th ACM Symp. On Theory of Computing. 143—152, 1972.

[2] D.S.Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9, 256—278, 1974.

[3] Gomory, Ralph E. (1958), «Outline of an algorithm for integer solutions to linear programs», Bulletin of the American Mathematical Society 64 (5): 275—279, doi:10.1090/S0002-9904-1958-10224-4.

[4] Dorit S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, page XV. PWS Publishing Company

[5] Tjark Vredeveld, Combinatorial approximation algorithms: Guaranteed versus experimental performance, Technische Universiteit Eindhoven, 2002, SBN 90-386-0532-3

[ausiello99complexity-6] а ^б ^в G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. — 1999.

[kann92onthe-7] а ^б ^в Viggo Kann. [1] — 1992. Архівовано з джерела 12 серпня 2021

[hastad99someoptimal-8] Johan Håstad. Some Optimal Inapproximability Results // Journal of the ACM : journal. — 1999. — 5 November. Архівовано з джерела 12 березня 2012. Процитовано 16 листопада 2020.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]