Set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms. Given a set of elements formula_1 (called the universe) and a collection formula_2 of formula_3 sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of formula_2 whose union equals the universe. For example, consider  the universe formula_5 and the collection of sets formula_6. Clearly the union of formula_2 is formula_8. However, we can cover all of the elements with the following, smaller number of sets: formula_9. More formally, given a universe formula_10 and a family formula_11 of subsets of formula_10, a "cover" is a subfamily formula_13 of sets whose union is formula_10. In the set covering decision problem, the input is a pair formula_15 and an integer formula_16; the question is whether there is a set covering of size formula_16 or less. In the set covering optimization problem, the input is a pair formula_15 , and the task is to find a set covering that uses the fewest sets. The decision version of set covering is NP-complete, and the optimization/search version of set cover is NP-hard. If each set is assigned a cost, it becomes a "weighted" set cover problem. Integer linear program formulation. The minimum set cover problem can be formulated as the following integer linear program (ILP). This ILP belongs to the more general class of ILPs for covering problems. The integrality gap of this ILP is at most formula_19, so its relaxation gives a factor-formula_19 approximation algorithm for  the minimum set cover problem (where formula_21 is the size of the universe). In weighted set cover, the sets are assigned weights. Denote the weight of set formula_22 by formula_23. Then the integer linear program describing weighted set cover is identical to the one given above, except that the objective function to minimize is formula_24. Hitting set formulation. Set covering is equivalent to the hitting set problem. That is seen by observing that an instance of set covering can be viewed as an arbitrary bipartite graph, with sets represented by vertices on the left, the universe represented by vertices on  the right, and edges representing the inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices. Greedy algorithm. There is a greedy algorithm for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest  number of uncovered elements. This method can be implemented in time linear in the sum of sizes of the input sets, using a bucket queue to prioritize the sets. It achieves an approximation ratio of formula_25, where formula_26 is the size of the set to be covered. In other words, it finds a covering that may be formula_27 times as large as the minimum one, where formula_27 is the formula_29-th harmonic number: formula_30 This greedy algorithm actually achieves an approximation ratio of formula_31 where formula_32 is the maximum cardinality set of formula_2. For formula_34dense instances, however, there exists a  formula_35-approximation algorithm for every formula_36. There is a standard example on which the greedy algorithm achieves an approximation ratio of formula_37. The universe consists of formula_38 elements. The set system consists of formula_16 pairwise disjoint sets formula_40 with sizes formula_41 respectively, as well as two additional disjoint sets formula_42, each of which contains half of the elements from each formula_43. On this input, the greedy algorithm takes the sets formula_44, in that order, while the optimal solution consists only of formula_45 and formula_46. An example of such an input for formula_47 is pictured on the right. Inapproximability results show  that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover up to lower order terms (see Inapproximability results below), under plausible complexity assumptions. A tighter analysis for the greedy algorithm shows that the approximation ratio is exactly formula_48. Low-frequency systems. If each element occurs in at most sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of using LP relaxation. If the constraint formula_49 is replaced by formula_50 for all in formula_11 in the integer linear program shown above, then it becomes a (non -integer) linear program . The algorithm can be described as follows: Inapproximability results. When formula_52 refers to the size of the universe, showed that set covering cannot be approximated in polynomial time to within a factor of formula_53, unless NP has quasi-polynomial time algorithms. Feige (1998) improved this lower bound to formula_54 under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. established a lower bound of formula_55, where formula_56 is a certain constant, under the weaker assumption that Pformula_57NP. A similar result with a higher value of formula_56 was recently proved by . showed  optimal inapproximability by proving that it cannot be approximated to formula_59 unless Pformula_60NP. Weighted set cover. Relaxing the integer linear program for weighted set cover stated above, one may use randomized rounding to get an formula_61-factor approximation. Non weighted set cover can be adapted to the weighted case.