Randomized Approximation Algorithms For The Maximum Vertex Cover Problem And Its Constrained Version

Both Set Cover(SC)and Vertex Cover(VC)are very famous NP-complete problems.They are also in Karp's 21 NP-Complete problems.Because of their wide applications in election,network design,bioinformatics and so on,these problems have been paid much attention by theoretical computer researchers.This paper studies their variation,the Maximum Coverage(MC)problem,Maximum Vertex Cover(MVC)problem and Partial Set Cover(PSC)problem.Maximum Coverage problem is defined as:given a base set S and a collection of its subsets SC,one needs to find no more than K subsets from SC to cover a maximum number of elements in S.In case that each element in S occurs no more than 2 times in SC,the problem becomes a variation of Vertex Cover problem,and is called Maximum Vertex Cover problem.Correspondingly,the subset-weighted and vertex-weighted version are called Maximum Weighted Coverage(MWC)problem and Maximum Weighted Vertex Cover(MWVC)problem respectively.By far,the best claimed approximation algorithms have a factor of(e-1)/e for MC and MWC,as well as 3/4 for MVC and MWVC[1].The input parameters for PSC and MC are the same,while in PSC,the goal is to select the minimum number of sets in SC to cover at least Kelements in S.Let f be the maximum frequency,or the maximum number of times an element appears in SC.The best approximation algorithm for PSC,developed 16 years ago,has a factor f.Aiming at the above problems,the main work of this paper is as follows:1.In this paper,we design an(e-1)/e-?-approximation algorithm for MC and an 3/4-?-approximation algorithm for MVC by LP-Rounding.Our algorithm uses a simple random rounding with a simple application of Chernoff bound in the analysis,which greatly simplifies the proof and could be useful for other related problems.Moreover,our algorithms can be extended to MWC and MWVC,keeping the same approximation factors using Hoeffding bound and the time complexity of our algorithm is polynomial besides solving a linear programming.Then we point out the unclear point in paper[1]for the MWVC.2.Next we give a bicriteria factor-(ln1/?,1-?)approximation algorithm,where? is related to 1/f,for a relaxed version of PSC where the bound on K is not a hard one.To be more precise,we use at most ln1/?.OPT number of sets to cover at least(1-?)·K number of elements in S.(This algorithm obviously works for Partial Line Cover.)Our method is based on a simple randomized rounding method,guaranteed with the Hoeffding inequality.3.At last we investigate the MVC problem for 3-bounded graphs(the degree of all vertices in the graph is bounded by 3)and cubic graphs(the degree of all vertices in the graph is exactly 3).The approximation ratio on cubic graphs is 21/25,which actually is 79/90 by analyzing the existence of a feasible solution for a linear programming system.This algorithm can also be extended to 3-bounded graphs,which guarantees an approximation factor of 19/24.On the negative result,we show that the MVC problem on both types of graph can't be approximated within.