Set Covering Problem Research

Given a domain E of n points, and a set S which contains m subsets of these points .Goal: find the fewest number of these subsets needed to cover all the points. This is the classic Set Cover Problem (SCP), which is also one of NP-Hard combinatorial optimization problems and one of the most well-studied problems. According to the hypothesis of P≠NP, there is no polynomial time algorithms of NP-Hard problems, therefore we can design approximation algorithm or approximated schemes for them.There are many variants of the set cover problem. If each set s in S has a positive weight w(s), the goal is also to get a sub set C of S, subject to the total weight in C is minimal. This is the Weighted Set Cover problem. The another variant is set cover problem with capacity constraints, or capacitated set cover problem, each set has a capacity k(s) associated it, meaning that the set s can cover at most k(s) points in E. Clearly the weighted Set Cover problem and capacitated Set Cover problem is at least as hard as Set Cover problem. Land and Yannakanis[11] showed that Set Cover has no approximation ratio cln(n)for c < 1/4 unless NP(?)⁽Dtime(n^polylogn)). Feige[3] improved this result and showed that an approximation ratio of (1 - o(l)) In(n) is not possibleunless NP(?)⁽Dtime(n^polylogn)), this is the newest bad news we knew.In recent years, research on algorithms for capacitated set coverproblem has been a focus of computer scientists, which is more valuable than general set cover problem in practice. The algorithm and complexity of application sub problem is the focus of the computer...