Design And Analysis Of Approximation Algorithms For Some Covering Problems

The thesis focuses on covering optimization problems under network background,aiming at the design of efficient algorithms with good approximation ratios.It contains four parts.The first part is motivated by wireless sensor network.The main problem is the maximum weight budgeted connected set cover problem(MWBCSC):given an element set E,a collection of sets S C(?)2E,a weight function w:E?R+,a cost function c:S?R+,a graph Gs on vertex set S,and a positive number L,the goal is to find a subcollection S'(?)S with maximum weight such that c(S')<L and the subgraph of Gs[S]induced by S is connected.For this problem,we obtain an 0(? log n)-approximation algorithm in general graph and an 0(logn)-approximation algorithm in unit disk graph,where ? is the maximum degree of the graph,n is the number of the sets.As far as we know,this is the first paper to give a performance guaranteed approximation algorithm for this problem.The second part is motivated by the influence propagation problem in a social net-work.The main problem is the minimum cost partial set multi-cover problem(PSMC):Given an element set E,a collection of sets S(?)2E,a cost function c:S?R+,a covering requirement function r:E? Z+,and a positive integer k,the minimum cost PSMC problem seeks a,subcollection S' C S with the minimum cost such that at least k elements are fully covered,in which element e is fully covered if e is covered by at least r(e)sets in S'.In order to solve PSMC,we give four algorit,hms.The first one is a simple greedy algorithm and obtains a ? approximation factor,where ? = max{|S|:S ? S}.The second one is a greedy algorithm with a dual fitting analysis.The performance ratio is at most O(H(?)),where the constant in O is related with many parameters and is meaningful only when k is very close to n.The third algorithm is a randomized algorithm and obtains approximation ratio at most 2k?(rmaxf)+ 2k? with a high probability,where f is the frequency of the element,i.e the maximum number of sets containing a same element,rmax is the maximum covering requirement,p is a submodular function related with the cost of sets,k? is a curvature of ?,which is used to measure the deviation of p from a modular function.The fourth algorithm uses local ratio method and obtains approximation ratio related with the minimum percentage of elements required to be fully covered during iterations of the algorithm.In particular,for the minimum partial(single)set cover problem and the minimum(full)set multi-cover problem,our algorithm has performance ratio f,coinciding with classic result.The third part studies the construction of virtual backbone in a wireless sensor net-work,which can be modeled as a special covering problem,d hop connected dominating set(MWdCDS):find a vertex set C(?)V(G)with the minimum cost such that the dis-tance between any vertex and C is at most d and C induces a connected subgraph.For MWdCDS,we give two algorithms.In the first one,we obtain approximation ratio at most d(??+?+1)H(?),where ? is the minimum connecting cost with distance at most d,? is the approximation ratio of the node weighted steiner tree problem,? is the maximum degree of the graph.The second algorithm outputs a feasible solution with approximation ratio at most ?(1 + dH(?))? where ? is the minimum connecting cost with distance at most 2d.The above studies show some non-linear features.In the fourth part,we study a non-linear combinatorial problem,which is the degree-balanced spanning tree problem:Given a graph G =(V,E),the goal is to find a spanning tree T such that ?v?V dT(v)2 is minimized,where dT(v)denotes the degree of node v in tree T.We prove that this problem is NP-hard,and then present a primal-dual based algorithm with approximation ratio at most max{4 + ?,4?2/2?-1+?},where ? is the maximum degree of the graph,? is an arbitrarily small positive number.