Naslov
Brzi aproksimacijski algoritmi za problem povezanog skupovnog pokrivača i srodne probleme
(Fast approximation algorithms for connected set cover problem and related problems)

Autori
Jelić, Slobodan

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
PMF-MO

Mjesto
Zagreb

Datum
28.05

Godina
2015

Stranica
102

Mentor
Matijević, Domagoj

Ključne riječi
skupovni pokrivač; povezani skupovni pokrivač; težinski povezani skupovni pokrivač; problem Steinerovog stabla na grupama; problem težinskog Steinerovog stabla na grupama; pokrivajuće Steinerovo stablo; problem frakcionalnog pakiranja i pokrivanja; randomizirani algoritam; derandomizirani algoritam; grafička procesorska jedinica opće namjene; aproksimacijski algoritam; sasvim polinomijalna aproksimacijska shema; Lagrangeova relaksacija; problem frakcionalnog Steinerovog stabla na grupama
(set cover; connected set cover; weighted connected set cover; group Steiner Tree; node weighted group Steiner Tree; covering Steiner Tree problem; fractional Packing and Covering linear programs; randomized algorithm; derandomized algorithm; generalpurpose graphics processing unit computation; approximation algorithm; fully polynomial time approximation scheme; Lagrangean relaxation; fractional group Steiner tree problem)

Sažetak
U disertaciji će biti prezentirani algoritmi za problem najmanjeg povezanog skupovnog pokrivača (nPSP) objavljeni u radu (Elbassioni, 2012). 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) (Garg, 2000). Prezentiran je i prvi aproksimacijski algoritam za težinsku verziju problema najmanjeg povezanog skupovnog pokrivača (Elbassioni, 2012). 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 (Jelic, 2015) 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 (Garg, 2000) 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 (Koufogiannakis, 2013) tako da približno rješava LP relaksaciju SSG-a.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA