Naslov Brzi aproksimacijski algoritmi za problem povezanog skupovnog pokrivača i srodne probleme Naslov (engleski) Fast approximation algorithms for connected set cover problem and related problems Autor Slobodan Jelić Mentor Domagoj Matijević (mentor)Član povjerenstva Robert Manger (predsjednik povjerenstva)Član povjerenstva Domagoj Matijević (član povjerenstva)Član povjerenstva Goranka Nogo (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2015-05-28, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Univerzalna decimalna klasifikacijaUDC ) 51 - Matematika Sažetak 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].
Sažetak (engleski) A first part of the contribution in this thesis consists of approximation algorithms for Minimum Connected Set Cover problem (MCSC) which are published in [28]. First, we present a polylogarithmic approximation algorithm for MCSC problem that uses an approximation algorithm for the group Steiner tree problem (GST) in [37]. We also give a first approximation algorithm for the weighted version of the problem [28]. MCSC problem with demands is also considered. A demand of each element determines the smallest number of sets in the solution that covers considered element. A second part of the contribution is related to the approximation algorithm for GST problem where the size of each group is bounded by some constant. This special cases remains NPhard since it generalizes Steiner tree problem. In the thesis a constant approximation algorithm for this problem will be studied. We also give approximation algorithms for some related problems. A third part of the contribution consists of an adaptation of the algorithm for solving packing and covering linear programs, which is presented in [52], to the parallel computing platform that is supported by modern graphic NVidia chips with CUDA. Instead of updating a single entry in the primal and dual solution vector per iteration, we update a few randomly chosen entries. A part of the contribution is related to deterministic updates of many entries in the primal and dual solution vector which is more amenable for parallelization. Although it increases time per iteration, an update of multiple entries in the primal and dual vectors in one iteration will make the primal and dual vectors converge to the optimal solution much faster which leads to a fewer number of iteration. Approximation algorithms for GST problem use algorithms for solving relaxation of natural integer programming formulation [37] for GST. After integrality constraints are relaxed, a linear program becomes the covering linear program where the number of constraints is an exponential function of the input size. In the thesis, the fully polynomial time approximation scheme from [52, 62] will be adopted such that it approximates a solution of the LP relaxation of GST [51].
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
Ključne riječi (engleski)
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
Jezik hrvatski URN:NBN urn:nbn:hr:217:865555 Studijski program Naziv: Matematika Vrsta resursa Tekst Opseg viii, 90 str. Način izrade datoteke Izvorno digitalna Prava pristupa Pristup korisnicima matične ustanove Uvjeti korištenja Datum i vrijeme pohrane 2019-03-08 12:59:21
