Approximation Algorithms For The Partial Prize-Collecting Vertex Cover Problems

Vertex cover problem is one of the classical NP-hard problems in combinatorial optimization.In this thesis,we study two variants of vertex cover problems:the k-prize-collecting vertex cover problem and the P-prize-collecting vertex cover problem.In the k-prize-collecting vertex cover problem,given a graph G=(V,E)and a positive integer k that is less than or equal to |E|.Every vertex i?V has a nonnegative cost ci.Every edge e E E has a nonnegative penalty cost ?e.The goal is to find a vertex set S(?)V that cover at least k edges with minimum total cost including the cost of vertices in S and the penalty cost of the edges not covered by S.In the P-prize-collecting vertex cover problem,given a graph G=(V,E)and a profit bound P.Every vertex i?V has a nonnegative cost ci.Every edge e?E has a nonnegative penalty cost ire and a nonnegative profit p,.The goal is to find a vertex set S(?)V such that the total cost,consisting of the cost of vertices in S and the penalty cost of the edges not covered by S,is minimized and the combined profit of the edges covered by S is at least P.In this thesis,we respectively design the approximate algorithms for the k-prize-collecting vertex cover problem and the P-prize-collecting vertex cover problem by using the primal dual scheme and Lagrange relaxation,and prove that the approximate ratios are 4+?,where ? is any fixed positive number.