FPTASlähestymistapoja

FPTASlähestymistapoja viittaa Approximate Polynomial Time -algoritmien (FPTAS) perheeseen. Nämä ovat algoritmistrategioita, joita käytetään ratkaisemaan NP-vaikeita optimointiongelmia. Vaikka NP-vaikeiden ongelmien tarkkojen ratkaisujen löytäminen voi viedä eksponentiaalisen ajan syötteen koon suhteen, FPTAS-algoritmit tarjoavat ratkaisun, jonka laskenta-aika on polynomi syötteen koon suhteen ja joka on "riittävän lähellä" optimaalista ratkaisua.

Tarkkuus FPTAS-algoritmeissa määritellään yleensä relatiivisella virheellä. FPTAS takaa, että löydetty ratkaisu on korkeintaan (1+ε)-kertainen optimaaliseen ratkaisuun nähden, missä ε on mielivaltaisen pieni positiivinen luku. Algoritmin laskenta-aika riippuu polynomisesti syötteen koosta ja eksponentiaalisesti luvusta 1/ε. Tämä tarkoittaa, että mitä pienempi ε on (eli mitä tarkempaa ratkaisua halutaan), sitä pidempi on algoritmin suoritusaika. FPTAS-lähestymistapoja ovat hyödyllisiä tilanteissa, joissa tarkka optimaalinen ratkaisu on laskennallisesti liian kallista saavuttaa, mutta hyvä approksimaatio riittää käytännön sovelluksiin. Esimerkkejä ongelmista, joihin FPTAS:ää voidaan soveltaa, ovat esimerkiksi reppuongelma (knapsack problem) ja useat aikataulutusongelmat.