Aproksimacioni algoritam

U računarskim naukama i operacionim istraživanjima, aproksimacioni algoritmi su algoritmi koji pronalaze aprokcimaciono rešenje za optimizaciju problema. Aproksimacioni algoritmi su često povezani sa NP-teškim problemima; jer je malo verovatno da će algoritam sa polinomijalnim vremenom biti efikasan i tačan u rešavanju NP-teških problema. Za razliku od heuristike, koja obično pronalazi razumno dobra rešenja razumno brzo, neko želi da dokaže kvalitet rešenja i Rantajm granice. Idealno, aproksimacija je optimalna do malog faktor (na primer u 5% optimalnih rešenja). Aproksimacioni algoritmi se povećano koriste za probleme gde algoritmi sa polinomijalnim-vremenom su poznati ali su preskupi zbog ulaznih podataka. Tipičan primer aproksimacionog algoritma je za pokrivača čvorova u grafu: pronaći neotkrivenu granu i dodaj oba kraja pokrivaču čvora, sve dok nijedna ostane. Jasno je da je dobijeni pokrivač najviše dvaputa veći optimalnog. Ovo je sa faktorom 2.

NP-teški problemi znatno se razlikuju u njihovoj aproksimaciji; neki, kao što je "Problem pakovanja u prostoru", mogu biti aproksimirani sa bilo kojim faktorom većim od 1 (kao familija aproksimacionih algoritama koja se još naziva polinomijalno-vreme-aproksimacione-šeme - PVAŠ). Drugi su nemogući za aproksimaciju sa bilo kojom konstantom, ili čak polinomijalnim faktorom P = NP (problem), kao što je maksimalan problem klika.

NP-teški problemi mogu često biti predstavljeni kao celobrojno programiranje koji se rešavaju u eksponencijalnom vremenu. Mnogi aproksimacioni algoritmi nastaju iz linearnog relaksacionog programiranja celobrojnog programiranja.

Nisu svi aproksimacioni algoritmi pogodni za sve praktične aplikacije. Oni se obično koriste IP/LP/Poluodređeni (Semidefinite) koji rešavaju, složene strukture podataka ili sofisticirane algoritamske tehnike koje vode do teškog implementiranja problema. Takođe, neki aproksimacioni algoritmi imaju nepraktični Ran-tajm čak i kad su polinomijalna vremena, na primer O(n²¹⁵⁶) . Ipak, studija čak veoma skupih algoritama nije skroz teorijsko traganje jer oni mogu da daju dragocene uvide. Klasičan primer je početni PVAŠ za Euklidov problem trgovačkog putnika (PTP) zbog Sanjeev Arora koji je imao prohibitivni Ran-tajm; ipak u roku od godinu dana Aurora je izmenio ideju u algoritam linearnog vremena. Takvi algoritmi su takođe korisni u nekim aplikacijama gde Ran-tajm i koštanje mogu biti opravdani, kao na primer Računarska biologija, finansijski inžinjering, planiranje transporta i upravljanje proizvodima. U takvim slučajevima, oni se moraju takmičiti sa odgovarajućim usmerenim IP formulacijama.

Drugo ograničenje pristupa je da se to odnosi samo na probleme optimizacije a ne na "čiste" problema odlučivanja kao zadovoljivosti , iako često je moguće zamisliti optimizaciju verzije tih problema, kao što je maksimalan problema zadovoljivosti.

Nepribližnost je plodno područje istraživanja u računarskoj teoriji kompleksnosti od 1990. god. Pošto je Aurora dokazao PCP teoremu godinu dana kasnije, pokazalo se da je Džonsonov algoritam aproksimacije iz 1974. god. postigao optimalni odnos aproksimacije, pod pretpostavkom da P! = NP.

Performanse garancije

Za neke aproksimacione algoritme moguće je dokazati odgovarajuće osobine optimalnog rešenja. Na primer, ρ-aproksimacioni algoritam A je algoritam za koji je dokazano da vrednost/cena f(x), približnog rešenja A(x) za dato x neće biti veće (ili manje, u zavisnosti od situacije) onda faktor ρ množi vrednost , OPT, optimalno rešenje.

${\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}}$

Faktor ρ se zove relativna performansa garancije. Aproksimacioni algoritam ima apsolutnu performansu garancije ili graničnu grešku c, ako je dokazano za svako x tako da

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

Slično, performansa garancije, R(x,y), rešenja y za neko x je definisano kao

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

gde f(y) je vrednost/cena rešenja y za neko x. Tačnije, performansa garancije je veća ili jednaka od 1 i jednaka 1 ako i samo ako y je optimalno rešenje. Ako algoritam A garantuje da će vratiti rešenje sa performansom garancije od najviše r(n), onda se za A kaže da je r(n)-aproksimacioni algoritam i ima aproksimacioni odnos od r(n). Isto tako, problem sa nekim r(n)-aproksimacioni algoritam, kaže se da je r(n)-približan ili ima približan odnos od r(n).

Može se primetiti da je za minimiziranje problema, dve različite garancije daju isti rezultat i da za maksimiziranje problema, relativne garancije performanse ρ predstavlja ekvivalent garanciji učinka $r=\rho ^{-1}$. U literaturi, obe definicije su česte, ali je jasno koja definicija se više koristi, za maksimiziranja problema, kao ρ ≤ 1, dok R ≥ 1.

Apsolutna performansa garancije $\mathrm {P} _{A}$ nekih približnih algoritama A, gde x predstavlja neki problem, i gde $R_{A}(x)$ je performansa garancije A od x (npr. ρ za neki problem x) je:

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

To znači da $\mathrm {P} _{A}$ je najveća granica aproksimacionog odnosa, r, takva da se vide sve moguće instance preko ovog problema. Isto tako je, asimptotska performansa odnosa $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\}.$

To znači da je isto kao apsolutna performansa odnosa, sa donjom granicom n sa veličinom problema. Ova dva tipa odnosa se koriste zato što postoje algoritmi gde razlike između ova dva odnosa su značajna.

Performanse garancije

	r-aproks.	ρ-aproks.	rel. greška	rel. greška	norm. rel. greška	aps. greška
maks: $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$
min: $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$

Algoritam tehnike projektovanja

Do sada postoji nekoliko standardnih tehnika koje neko pokušava da dizajnira aproksimacijom algoritama. Oni obuhvataju sledeće.

1. Pohlepni algoritam
2. Lokalna pretraga
3. Nabrajanje i dinamičko programiranje
4. Rešavanje konveksnog programiranja relaksacije da bismo dobili frakciono (raѕlomačko) rešenje. Onda konvertovanje raѕlomačkog rešenja u izvodljivo rešenje odgovarajućim zaokruživanjem. Poznata relaksacija uključuje sledeće.
   1. Linearno programiranje relaksacije
   2. Poludefinisano programiranje relaksacije
5. Ugrađivanje problema u neko jednostavnu metrikz, a zatim rešavanje problema na metrici. Ovo je takođe poznato kao metrika ugradnje.

Epsilon uslovi

U literaturi, približan odnos za maksimiѕaciju (minimizaciju) problema c - ϵ (min: c + ϵ) znači da algoritam ima približan odnos c ∓ ϵ za proizvoljno ϵ > 0 ali odnos ne može (ne sme) biti prikazan za ϵ = 0. Primer za ovo je optimalna nepribližnost — nepostojanje približnosti — odnos 7 / 8 + ϵ za zadovoljiv MAX-3SAT. Kao što je pomenuto ranije, kada je c = 1, kaže se da problem ima polinomijalno-vreme-aproksimacije-šeme.

Neki ϵ-slučaj se može pojaviti kada približni algoritam uvodi u multiplikativne i konstantne greške dok najmanji optimalni slučaj veličine n teži ka beskonačnosti kako n raste. U ovom slučaju, približni odnos je c ∓ k / OPT = c ∓ o(1) za neke konstante c i k. Za proizvoljno ϵ > 0, može se izabrati dovoljno veliki N takav da k / OPT < ϵ za svako n ≥ N. Za svako fiksirano ϵ, primeri veličine n < N se mogu rešiti Pohlepnim algoritmom , čime se pokazuje aproksimacija odnosa — postojanje aproksimacije algoritama sa garancijom — of c ∓ ϵ za svako ϵ > 0.

Vidi još

• Analiza dominacije smatra garancije u pogledu ranga kompjuterizovanih rešenja
• PVAŠ - tip približavanja algoritam koji uzima odnos približavanja kao parametar
• APX klasa problema sa nekim konstantnim-faktor približavanja algoritma
• Aproksimacija smanjenja očuvanja
• Tačan algoritam

Literatura

• 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. str. 1022—1056.
• Dorit S. Hochbaum, ur. (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. 

Spoljašnje veze

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