Brzi aproksimacijski algoritmi za problem povezanog skupovnog pokrivača i srodne probleme

doctoral thesis

• Title (english): Fast approximation algorithms for connected set cover problem and related problems
• Author: Slobodan Jelić
• Mentor: Domagoj Matijević (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Domagoj Matijević (član povjerenstva)
• Committee member: Goranka Nogo (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2015-05-28, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics
• Universal decimal classification (UDC): 51 - Mathematics

Abstract

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].

Abstract (english)

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].

• Keywords: 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
• Keywords (english): 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
• Language: croatian
• URN:NBN: urn:nbn:hr:217:865555
• Study programme: Title: Mathematics; Study programme type: university; Study level: postgraduate; Academic / professional title: doktor/doktorica znanosti, područje prirodnih znanosti, polje matematika (doktor/doktorica znanosti, područje prirodnih znanosti, polje matematika)
• Type of resource: Text
• Extent: viii, 90 str.
• File origin: Born digital
• Access conditions: Access restricted to students and staff of home institution
• Created on: 2019-03-08 12:59:21