Fast approximation algorithms for connected set cover problem and related problems

Jelić, Slobodan (2015) Fast approximation algorithms for connected set cover problem and related problems. Doctoral thesis, Faculty of Science > Department of Mathematics.

[img] PDF
Restricted to Registered users only
Language: Croatian

Download (3MB) | Request a copy


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

Item Type: Thesis (Doctoral thesis)
Keywords: 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
Supervisor: Matijević, Domagoj
Date: 2015
Number of Pages: 90
Subjects: NATURAL SCIENCES > Mathematics
NATURAL SCIENCES > Mathematics > Algebra
NATURAL SCIENCES > Mathematics > Mathematical Logic and Accounting
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 02 Jul 2015 09:24
Last Modified: 02 Jul 2015 09:24

Actions (login required)

View Item View Item