Approksimaatiosuhde

Approksimaatiosuhde (engl. approximation ratio) on mittari, jolla kuvataan algoritmin ratkaisuun vertaansa optimiin liittyvää laatua optimointiongelmissa. Kun täydellisen ratkaisun löytäminen on käytännössä epärealistista suurissa tapauksissa, approksimaatiosuhde kertoo, kuinka hyvin käytetty algoritmi lähestyy parasta mahdollista ratkaisua.

Formalisoitu määritelmä jakautuu minimointi- ja maksimoimiselle ongelmille. Olkoon I ongelman instance, A(I) algoritmin tuottama arvo ja OPT(I) optimaalinen arvo. Minimoivassa ongelmassa, jos on vakio r ≥ 1, jolla A(I) ≤ r · OPT(I) kaikilla I, sanotaan, että algoritmi on r-approksimaatio ja approksimaatiosuhde on r. Maksimoivassa ongelmassa samoin sanotaan, että on r-approksimaatio, jos A(I) ≥ OPT(I) / r kaikilla I (eli OPT(I) / A(I) ≤ r). On myös käytössä additive-variantti, jossa A(I) − OPT(I) ≤ δ jossain δ:llä, mutta se ei ole yhtä yleinen kuin multiplicatiivinen määritelmä.

Approksimaatiosuhteen käsite toimii yhdessä tutkimuksen kanssa, jossa tavoitteena on kehittää tehokkaita algorithmeja, joilla on karkeasti hallittu etäisyys optimaalisesta ratkaisusta. Toisaalta tutkimus toisinaan osoittaa, ettei tietyn ratkaisun r-approksimaatio ole mahdollista kovin pienellä r, mikä johtaa inapproximability-tuloksiin ja rajauksiin.

Esimerkkejä tunnetuista tuloksista: Vertex Coverin 2-approximation, Set Coverin ln n -tyyppinen käyttäytyminen sekä metrinen TSP:n 1,5-approximaatio (Christofides’n algoritmi). Nämä suuntaukset vaikuttavat sekä teoreettiseen että käytännön suunnitteluun.

Lyhyesti, approksimaatiosuhde mittaa, kuinka paljon algoritmin ratkaisu häviää optimiin nähden, ja toimii keskeisenä mittarina approximatiivisissa algoritmeissa sekä analyysissä että kehitystyössä.