2approksimaatio

2-approksimaatio, tai 2approksimaatio, viittaa algoritmiseen lähestymistapaan optimoinnissa, jossa ratkaisu on suhteessa optimaaliin seuraavasti: minimointiongelmissa tulos on enintään kaksinkertainen optimaaliin, maksimoitavissa ongelmissa taas tulos on vähintään puolet optimaalisesta. Tällaiset algoritmit ovat polynomiajassa suoritettavia ja tarjoavat luotettavan laatutakuun.

Formaalisti: Olkoon I annettu optimointiongelma ja OPT(I) sen optimaali arvo. Algoritmi A on 2-approksimaatio minimointiin, jos jokaisessa I:ssä A(I) ≤ 2 · OPT(I). Maksimoitavalle ongelmalle A on 1/2-approksimaatio, eli A(I) ≥ (1/2) · OPT(I).

Esimerkki: Vertex Cover -ongelma. Graafille G = (V,E) etsitään pienintä kattavaa joukkoa. Valitaan maksimaalinen ottelu M graafista. Oletetaan C = endpoints(M). C on kattava, sillä jokaisesta reunasta on vähintään yksi päätepiste C:ssä. Koska ottelu on maksimaalinen, |C| = 2|M| ja OPT ≥ |M|, joten |C| ≤ 2 OPT. Näin C on 2-approksimaatio Vertex Coveriin, ja sen laskeminen on polynomiaalista.

Yleisesti 2-approksimaatiot tarjoavat yksinkertaisen ja luotettavan tavan saada laadukkaita ratkaisuja, mutta ne eivät aina ole paras mahdollinen ratkaisutapa kaikille ongelmille. Joillakin ongelmilla on tunnettuja inapproximability-tuloksia, jotka rajoittavat mahdollisuuksia parantaa 2-rajasta ilman ratkaisuun liittyviä ratkaisevia oletuksia. Silti 2-approksimaatio toimii yleisesti hyvänä perustasoa laajasti käytetyissä sovelluksissa.