Approximation Algorithm For Minimum Connected 3-path Vertex Cover And Partial Set Multicover

Covering problems are very famous combinatorial optimization problems.Being two notable problems in Karp's 21 NP-complete problems,vertex cover problem and set coverproblem are well known by researchers in theoretical computer science and extensively studied.In this thesis,we study two covering problems: connected k-path vertex cover and partial set multicover.The connected k-path vertex cover problem has its background in the field of security and supervisory in wireless sensor networks?WSNs?.A vertex subset S of a given graph G =?V,E? is called a connected k-path vertex cover?CVCP_k?if every k-path of G contains at least one vertex from S,and the subgraph of G induced by S is connected.The minimum partial set multicover problem?PSMC?is a,combination of the set multicover problem?SMC?and the partial set cover problem?PSC? problem.Given a set of elements E,a collection S of subsets of E,a positive cost wsfor eachset S?S,a positive integer covering requirement re for each element e?E and a real number 0 <?< 1,the PSMC problem asks for a minimum cost sub-collection F???S to fully cover at least pn elements,where n is the number of elements,and an element e is fully covered by F if it belongs to at least r_e sets of F.This paper consists of four chapters.In the first chapter,we introduce the basic notations,backgrounds and research status of CVCP_k and PSMC.In the second chapter,we present an approximation algorithm for CVCP₃ with performance ratio 2?+ 1/2,where ? is the performance ratio for VCP₃?without connectivity requirement?.In the third chapter,we present a greedy algorithm for PSMC,and analyze the ratio between the cost of the computed solution and the cost of an optimal solution to the corresponding?full?SMC problem.We call this ratio as a partial-versus-full ratio.It turns out that the partial-versus-full ratio of our algorithm is at most Inr/l-?,where r is the maximum covering requirement of an element,and p is the fraction of elements required to be fully covered.Experiments show the advantage of using partial cover to replace full cover.In the forth chapter,we make a discussion and conclusion of our results and methods.