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
PTAS (polynomiaalinen aproksimaatiosuunnitelma) ja FPTAS (täysin polynomiaalinen aproksimaatiosuunnitelma) ovat tärkeitä luokkia. PTAS tuottaa (1+ε)-läheisen ratkaisun minkä
Yleisimmät tekniikat ovatGreedyn ja paikallisen haun menetelmät, LP-relaxaatioiden ja tulkinnan/runderoinnin menetelmät sekä primal-dual- ja satunnaistamistekniikat. Tyypillisiä
Aproksimaatioalgoritmeilla on sekä käytännön sovelluksia että rajoituksia: joillakin ongelmilla on tiukat matemaattiset ala-rajat, eikä niiden saavutusta