U disertaciji će biti prezentirani algoritmi za problem najmanjeg povezanog skupovnog pokrivača (nPSP) objavljeni u radu [28]. U prvom redu bit će prezentiran aproksimacijski algoritam za problem nPSP s polilogaritamskim aproksimacijskim omjerom koji koristi aproksimacijski algoritam za problem Steinerovog stabla na grupama (SSG) [37]. Prezentiran je i prvi aproksimacijski algoritam za težinsku verziju problema najmanjeg povezanog skupovnog pokrivača [28]. Razmatrat će se i verzija ovog problema sa zahtjevima na svakom elementu koji određuju koliko najmanje skupova u rješenju treba pokrivati pojedini element. Drugi dio doprinosa odnosi se na aproksimacijski algoritam za SSG kod kojeg je veličina grupe omeđena konstantom. Ovaj specijalni slučaj SSG-a ostaje i dalje NP-težak s obzirom da poopćuje Steiner tree problem. U disertaciji će biti prezentiran algoritam koji daje približno rješenje problema s konstantnim aproksimacijskim omjerom. Pored toga, razmatrat će se aproksimacije nekih srodnih problema. Treći dio doprinosa ove disertacije sastoji se u adaptaciji algoritma za rješavanje linearnih programa pakiranja i pokrivanja izloženog u [52] na paralelni način računanja koji podržavaju moderne NVidia grafičke kartice s CUDA arhitekturom. Umjesto povećavanja vrijednosti jedne varijable u primalu i jedne varijable u dualu, povećat će se nekoliko slučajno izabranih varijabli. Dio doprinosa odnosi se i na deterministički način povećavanja više varijabli u primalu i dualu istovremeno, što se pokazalo prihvatljivijim pristupom prilikom paralelizacije. Iako povećavanja više varijabli u primalu i dualu istovremeno zahtjeva više vremena po iteraciji, takav pristup osigurava bržu konvergenciju primalnog i dualnog rješenja ka optimalnom, što smanjuje ukupan broj iteracija algoritma. Aproksimacijski algoritmi za SSG koriste algoritme za rješavanje relaksacije prirodnog cjelobrojnog linearnog programa [37] kojim je modeliran SSG. Nakon relaksiranja uvjeta cjelobrojnosti dobivamo linearni program pokrivanja s naglaskom da je broj uvjeta eksponencijalna funkcija veličine instance SSG-a. U disertaciji će biti adaptirana sasvim polinomijalna aproksimacijska shema iz [52, 62] tako da približno rješava LP relaksaciju SSG-a [51].