Aproksimaatioalgoritmeilla
Aproksimaatioalgoritmeilla ovat algoritmeja, jotka pyrkivät löytämään optimaalisen ratkaisun ongelmaan, mutta sen sijaan palauttavat ratkaisun, joka on lähellä optimaalista. Nämä algoritmit ovat erityisen hyödyllisiä tilanteissa, joissa optimaalisen ratkaisun löytäminen on laskennallisesti liian kallista tai aikaa vievää. Monet NP-vaikeat ongelmat, kuten kauppamatkustajan ongelma tai satunnainen leikkausongelma, kuuluvat tähän luokkaan.
Aproksimaatioalgoritmien tavoitteena on tarjota ratkaisu, jonka laatu on taattu jollain tavalla suhteessa optimaaliseen ratkaisuun. Tämä laadun
Approksimaatioalgoritmeja voidaan luokitella eri tavoin, kuten polymoorialaiksi approksimaatioalgoritmeiksi (PTAS) tai täydellisiksi approksimaatioalgoritmeiksi (FPTAS), jotka tarjoavat parempia