Aproximaatioalgoritmit

Aproksimaatioalgoritmit ovat optimointiongelmien ratkaisutapoja, joissa tarkka optimi ratkaisu ei useimmiten ole saatavilla tehokkaasti suurissa tapauksissa. Tavoitteena on löytää ratkaisu, joka on mahdollisimman lähellä optimaalista ja jossa ratkaisun etu sekä ratkaisuajan ovat hallittavissa. Usein ongelma on NP-hard, jolloin suuria ongelmia varten ei ole tunnettuja nopeita täsmäratkaisuja.

Takuut aproksimaatioalgoritmeille ilmaistaan yleensä suhteellisella mittayksiköllä, niin sanotulla multiplikatiivisella tai lisäarvotakuulla. Multiplicatiivinen takuu kertoo, että ratkaisu A on aina oltava korkeintaan tietyn kertoimen α∙OPT tai vähintään 1/α-kerta OPT riippuen siitä, onko kyse minimointi- vai maksimointitehtävästä. Lisäarvotakuussa ero on, että A ≤ OPT + β (minimointi) tai A ≥ OPT − β (maksimoiminen). Monet tulokset ovat sekä käytännöllisiä että teoreettisesti perusteltuja.

PTAS (polynomiaalinen aproksimaatiosuunnitelma) ja FPTAS (täysin polynomiaalinen aproksimaatiosuunnitelma) ovat tärkeitä luokkia. PTAS tuottaa (1+ε)-läheisen ratkaisun minkä tahansa ε>0 annettuna, ja sen ajoaika on polynomiaalinen paitsi ε:n käänteisessä luvussa, kun taas FPTAS on polynomiaalinen sekä syötteen koolle että 1/ε:lle.

Yleisimmät tekniikat ovatGreedyn ja paikallisen haun menetelmät, LP-relaxaatioiden ja tulkinnan/runderoinnin menetelmät sekä primal-dual- ja satunnaistamistekniikat. Tyypillisiä esimerkkejä ovat jäsentelyt kuten Vertex Cover (kaksois-approximaatio), Set Cover (moninkertainen skaalauslikkaus), Knapsack (FPTAS), sekä sarja klassikkoja kuten TSP-tapaus, jonka matriisillisen rajoituksia hyödyntävillä lähestymistavoilla on jo merkittäviä tuloksia.

Aproksimaatioalgoritmeilla on sekä käytännön sovelluksia että rajoituksia: joillakin ongelmilla on tiukat matemaattiset ala-rajat, eikä niiden saavutusta voi parantaa alle tietyn rajan ilman pavedkijöitä. PCP-teoreemien tulokset määrittelevät tietyt esteet hyvän approksimaation rajoille.