Smart Algorithms For Covering Problems

Connected dominating set is a widely adopted model for the virtual backbone of a wireless sensor network.In this thesis,we design an evolutionary algorithm for the minimum connected dominating set problem(MinCDS),whose performance is theoret-ically guaranteed in terms of both computation time and approximation ratio.Given a connected graph G=(V,E),a connected dominating set(CDS)is a subset C(?)V such that every vertex in V\C has a neighbor in C,and the subgraph of G induced by C is connected.The goal of MinCDS is to find a CDS of G with the minimum cardinality.We show that our evolutionary algorithm can find a CDS in expected O(n3)time which approximates the optimal value within factor(2+ln ?),where n and ? are the number of vertices and the maximum degree of graph G,respectively.In order to improve the fault tolerance of virtual backbone,(k,m)-CDS was proposed by some researchers.Given a graph G=(V,E),a vertex set C(?)V is a(k,m)-CDS if every vertex in V\C is adjacent with at least m vertices of C,and the subgraph of G induced by C,denoted as G[C]],is k-connected.In this paper,we design an evolutionary algorithm for the minimum(2,m)-CDS problem with m? 2,which finds a(2,m)-CDS in expected O(n4)time which approximates the optimal value within factor ?+2(1+ln ?),where ? is the approximation ratio for the minimum(1,m)-CDS problem.In the above studies,the approximate ratio obtained by the EA is coincides with the best known ratio obtained by the centralized greedy algorithm.It reveals the underlying connection between evolutionary algorithms and approximate algorithms.The dominating set problem is a special coverage problem.This thesis also discusses how to find a superior solution for coverage problem by multi-agent games.We propose a set cover game and show that any Nash equilibrium is a minimal set cover,and also a Pareto optimal solution.Then we present a distributed algorithm to realize the game.The algorithm is self-organinzing in the sense that all players can make decisions by them-selves simultaneously.It is local in the sense that each player makes his decision based only on information in his neighborhood.It is efficient in the sense that it converges to a minimal set cover in polynomial time when cmax/cmin is upper bounded by a polynomial of the input size,where cmax and cmin are the maximum cost and the minimum cost of sets,respectively.