Approximation Algorithm For Minimum Weight Connected Set Cover

Set cover problem is one of the classic problems in the field of combinatorial optimization,which asks to choose a subcollection from a given set collection to cover all elements.Besides theoretical research,it also significant in real world.This paper studies the Minimum Weight Partial Connected Set Cover problem(PCSC)and 3-path vertex cover problem.For MWPCSC problem,given an element set U,a collection S of subsets of U,a weight function c:S?Q+,a connected graph Gs on vertex set S,and a positive integer k ? |U|,the goal is to find a minimum weight subcolletion S'(?)S such that the subgraph of G induced by S' is connected,|US?S'S|?k.If the graph Gs has the property that any two sets with a common element has hop distance at most r in Gs,then the problem is called r-hop PCSC.We presented an O(ln(m + n))-approximation algorithm for the minimum weight 1-hop PCSC problem and an O(ln(m + n))-approximation algorithm for the minimum cardinality r-hop PCSC problem.Our performance ratio improves previous results and our method is much simpler than previous methods.For the special set cover problem,the 3-path vertex cover problem,a vertex set C of graph G =(V,E)is a 3-path vertex cover if every path on 3 vertices has at least one vertex in C.This paper studies the online version of the minimum 3-path vertex cover problem,in which vertices are revealed one by one,and one has to determine whether the newly revealed vertex should be chosen into the solution without knowing future information.We show that a natural algorithm has competitive ratio at most?,where ? is the maximum degree of the graph.An example is given showing that the ratio is tight.