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

У рачунарским наукама и операционим истраживањима, апроксимациони алгоритми су алгоритми који проналазе апрокцимационо решење за оптимизацију проблема. Апроксимациони алгоритми су често повезани са НП-тешким проблемима; јер је мало вероватно да ће алгоритам са полиномијалним временом бити ефикасан и тачан у решавању НП-тешких проблема. За разлику од хеуристике, која обично проналази разумно добра решења разумно брзо, неко жели да докаже квалитет решења и Рантајм границе. Идеално, апроксимација је оптимална до малог фактор (на пример у 5% оптималних решења). Апроксимациони алгоритми се повећано користе за проблеме где алгоритми са полиномијалним-временом су познати али су прескупи због улазних података. Типичан пример апроксимационог алгоритма је за покривача чворова у графу: пронаћи неоткривену грану и додај оба краја покривачу чвора, све док ниједна остане. Јасно је да је добијени покривач највише двапута већи оптималног. Ово је са фактором 2.

НП-тешки проблеми знатно се разликују у њиховој апроксимацији; неки, као што је "Проблем паковања у простору", могу бити апроксимирани са било којим фактором већим од 1 (као фамилија апроксимационих алгоритама која се још назива полиномијално-време-апроксимационе-шеме - ПВАШ). Други су немогући за апроксимацију са било којом константом, или чак полиномијалним фактором П = НП (проблем), као што је максималан проблем клика.

НП-тешки проблеми могу често бити представљени као целобројно програмирање који се решавају у експоненцијалном времену. Многи апроксимациони алгоритми настају из линеарног релаксационог програмирања целобројног програмирања.

Нису сви апроксимациони алгоритми погодни за све практичне апликације. Они се обично користе IP/LP/Полуодређени (Semidefinite) који решавају, сложене структуре података или софистициране алгоритамске технике које воде до тешког имплементирања проблема. Такође, неки апроксимациони алгоритми имају непрактични Ран-тајм чак и кад су полиномијална времена, на пример O(n^2¹⁵⁶)^[1] . Ипак, студија чак веома скупих алгоритама није скроз теоријско трагање јер они могу да дају драгоцене увиде. Класичан пример је почетни ПВАШ за Еуклидов проблем трговачког путника (ПТП) због Сањеев Арора који је имао прохибитивни Ран-тајм; ипак у року од годину дана Аурора је изменио идеју у алгоритам линеарног времена. Такви алгоритми су такође корисни у неким апликацијама где Ран-тајм и коштање могу бити оправдани, као на пример Рачунарска биологија, финансијски инжињеринг, планирање транспорта и управљање производима. У таквим случајевима, они се морају такмичити са одговарајућим усмереним IP формулацијама.

Друго ограничење приступа је да се то односи само на проблеме оптимизације а не на "чисте" проблема одлучивања као задовољивости , иако често је могуће замислити оптимизацију верзије тих проблема, као што је максималан проблема задовољивости.

Неприближност је плодно подручје истраживања у рачунарској теорији комплексности од 1990. год. Пошто је Аурора доказао ПЦП теорему годину дана касније, показало се да је Џонсонов алгоритам апроксимације из 1974. год. постигао оптимални однос апроксимације, под претпоставком да П! = НП.

Перформансе гаранције

За неке апроксимационе алгоритме могуће је доказати одговарајуће особине оптималног решења. На пример, ρ-апроксимациони алгоритам А је алгоритам за који је доказано да вредност/цена f(x), приближног решења A(x) за дато x неће бити веће (или мање, у зависности од ситуације) онда фактор ρ множи вредност , OPT, оптимално решење.

{\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}

Фактор ρ се зове релативна перформанса гаранције. Апроксимациони алгоритам има апсолутну перформансу гаранције или граничну грешку c, ако је доказано за свако x тако да

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

Слично, перформанса гаранције, R(x,y), решења y за неко x је дефинисано као

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

где f(y) је вредност/цена решења y за неко x. Тачније, перформанса гаранције је већа или једнака од 1 и једнака 1 ако и само ако y је оптимално решење. Ако алгоритам A гарантује да ће вратити решење са перформансом гаранције од највише r(n), онда се за A каже да је r(n)-апроксимациони алгоритам и има апроксимациони однос од r(n). Исто тако, проблем са неким r(n)-апроксимациони алгоритам, каже се да је r(n)-приближан или има приближан однос од r(n).^[2]^[3]

Може се приметити да је за минимизирање проблема, две различите гаранције дају исти резултат и да за максимизирање проблема, релативне гаранције перформансе ρ представља еквивалент гаранцији учинка $r=\rho ^{-1}$ . У литератури, обе дефиниције су честе, али је јасно која дефиниција се више користи, за максимизирања проблема, као ρ ≤ 1, док Р ≥ 1.

Апсолутна перформанса гаранције $\mathrm {P} _{A}$ неких приближних алгоритама A, где x представља неки проблем, и где $R_{A}(x)$ је перформанса гаранције A од x (нпр. ρ за неки проблем x) је:

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

То значи да $\mathrm {P} _{A}$ је највећа граница апроксимационог односа, r, таква да се виде све могуће инстанце преко овог проблема. Исто тако је, асимптотска перформанса односа $R_{A}^{\infty }$ is:

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

То значи да је исто као апсолутна перформанса односа, са доњом границом n са величином проблема. Ова два типа односа се користе зато што постоје алгоритми где разлике између ова два односа су значајна.

Перформансе гаранције
	r-апрокс.^[2]^[3]	ρ-апрокс.	рел. грешка^[3]	рел. грешка^[2]	норм. рел. грешка^[2]^[3]	апс. грешка^[2]^[3]
макс: $f(x)\geq$	$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$
мин: $f(x)\leq$	$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 - ϵ (мин: c + ϵ) значи да алгоритам има приближан однос c ∓ ϵ за произвољно ϵ > 0 али однос не може (не сме) бити приказан за ϵ = 0. Пример за ово је оптимална неприближност — непостојање приближности — однос 7 / 8 + ϵ за задовољив MAX-3SAT. Као што је поменуто раније, када је c = 1, каже се да проблем има полиномијално-време-апроксимације-шеме.

Неки ϵ-случај се може појавити када приближни алгоритам уводи у мултипликативне и константне грешке док најмањи оптимални случај величине n тежи ка бесконачности како n расте. У овом случају, приближни однос је c ∓ k / OPT = c ∓ o(1) за неке константе c и k. За произвољно ϵ > 0, може се изабрати довољно велики N такав да k / OPT < ϵ за свако n ≥ N. За свако фиксирано ϵ, примери величине n < N се могу решити Похлепним алгоритмом , чиме се показује апроксимација односа — постојање апроксимације алгоритама са гаранцијом — of c ∓ ϵ за свако ϵ > 0.

Види још

Анализа доминације сматра гаранције у погледу ранга компјутеризованих решења
ПВАШ - тип приближавања алгоритам који узима однос приближавања као параметар
APX класа проблема са неким константним-фактор приближавања алгоритма
Апроксимација смањења очувања
Тачан алгоритам

Референце

^ Zych, Anna; Bilò, Davide (2011). „New Reoptimization Techniques applied to Steiner Tree Problem”. Electronic Notes in Discrete Mathematics. 37: 387—392. ISSN 1571-0653. doi:10.1016/j.endm.2011.05.066.
^ ^а ^б ^в ^г ^д G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela & M. Protasi (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.
^ ^а ^б ^в ^г ^д Kann, Viggo (1992). On the Approximability of NP-complete Optimization Problems (PDF).

Литература

Kann, Viggo (1992). On the Approximability of NP-complete Optimization Problems (PDF).
G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela & M. Protasi (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.
Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 978-3-540-65367-7.
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. Chapter 35: Approximation Algorithms. стр. 1022—1056.
Dorit S. Hochbaum, ур. (1997). Approximation Algorithms for NP-Hard problems. PWS Publishing Company. ISBN 978-0-534-94968-6. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More
Williamson, David P.; Shmoys, David B. (26. 4. 2011). The Design of Approximation Algorithms. Cambridge University Press. ISBN 978-0521195270.

Спољашње везе

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

[ZychBilò2011-1] Zych, Anna; Bilò, Davide (2011). „New Reoptimization Techniques applied to Steiner Tree Problem”. Electronic Notes in Discrete Mathematics. 37: 387—392. ISSN 1571-0653. doi:10.1016/j.endm.2011.05.066.

[ausiello99complexity-2] а ^б ^в ^г ^д G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela & M. Protasi (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.

[kann92onthe-3] а ^б ^в ^г ^д Kann, Viggo (1992). On the Approximability of NP-complete Optimization Problems (PDF).

[1]

[2]

[3]