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. Given a set of elements (called the universe) and a collection of sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of whose union equals the universe. For example, consider the universe and the collection of sets Clearly the union of is . However, we can cover all of the elements with the following, smaller number of sets: More formally, given a universe and a family of subsets of , a cover is a subfamily of sets whose union is . In the set covering decision problem, the input is a pair and an integer ; the question is whether there is a set covering of size or less. In the set covering optimization problem, the input is a pair , 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. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms. 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 , so its relaxation gives a factor- approximation algorithm for the minimum set cover problem (where is the size of the universe). In weighted set cover, the sets are assigned weights. Denote the weight of set by . Then the integer linear program describing weighted set cover is identical to the one given above, except that the objective function to minimize is . 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 the universe represented by vertices on the left, the sets 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 right-vertices which covers