Approksimaatioalgoritmeja

Approksimaatioalgoritmit ovat algoritmeja, jotka ratkaisevat yhdistelmäoptimoinnin ongelmia tehokkaasti tuottamalla ratkaisun, jonka arvo on lähellä parasta mahdollista. Ne ovat erityisen hyödyllisiä ongelmissa, joiden täsmällinen ratkaisu on laskennallisesti epäkäytännöllinen suurilla syötteillä (yleisesti NP-hard).

Laatutakuut tyypillisesti määritellään approximaatio-kertoimella α: minimointiongelmissa ratkaisu A(I) ≤ α·OPT(I) kaikilla I; maksimointiongelmissa ratkaisu A(I) ≥ OPT(I)/α. α voi olla vakio tai riippua ongelmasta. Takaus annetaan useimmiten worst-case -tasolla, ja joissain tapauksissa myös paremman keskimääräisen suorituskyvyn kuvaamiseksi.

Yleisimmät lähestymistavat ovat greedily-algoritmit (kenkien ja muiden päätösten tekeminen kiinnostavilla kustannuksilla), LP-relaksaatio ja pyöristäminen, primal-dual -menetelmät sekä lokaali haku ja satunnaistettu lähestymistapa. Lisäksi moniin ongelmiin voidaan soveltaa PTAS- tai FPTAS-lähestymistapoja: PTAS antaa (1+ε)-läheisyyden suurella ajalla, ja FPTAS samoin mutta ajassa riippuvaisessa suhteessa 1/ε.

Esimerkkejä tunnetuista ongelmista: Set cover tarjoaa ln n -tasaisen approksimaation; Vertex cover on 2-approx; Metric TSP tarjoaa noin 1,5-approksimaatio; Knapsackilla on FPTAS-takuut ja joidenkin erikoistapausten PTAS.

Sovelluksia ovat verkkojen suunnittelu, resurssien jakaminen, aikataulutus ja toimitusketjujen optimointi. Rajoitteisiin kuuluu, ettei kaikille ongelmille ole hyvää kertalukua, ja joitakin ongelmia on todettu impossible- tai inapproximability-tuloksilla, jos P vs NP-asetelma pidetään ratkaisemattomana.