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. 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 { 1 , 2 , . . . , n } {displaystyle {1,2,...,n}} (called the universe) and a collection S {displaystyle S} of m {displaystyle m} sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of S {displaystyle S} whose union equals the universe. For example, consider the universe U = { 1 , 2 , 3 , 4 , 5 } {displaystyle U={1,2,3,4,5}} and the collection of sets S = { { 1 , 2 , 3 } , { 2 , 4 } , { 3 , 4 } , { 4 , 5 } } {displaystyle S={{1,2,3},{2,4},{3,4},{4,5}}} . Clearly the union of S {displaystyle S} is U {displaystyle U} . However, we can cover all of the elements with the following, smaller number of sets: { { 1 , 2 , 3 } , { 4 , 5 } } {displaystyle {{1,2,3},{4,5}}} . More formally, given a universe U {displaystyle {mathcal {U}}} and a family S {displaystyle {mathcal {S}}} of subsets of U {displaystyle {mathcal {U}}} ,a cover is a subfamily C ⊆ S {displaystyle {mathcal {C}}subseteq {mathcal {S}}} of sets whose union is U {displaystyle {mathcal {U}}} . In the set covering decision problem, the input is a pair ( U , S ) {displaystyle ({mathcal {U}},{mathcal {S}})} and an integer k {displaystyle k} ; the question is whetherthere is a set covering of size k {displaystyle k} or less. In the set covering optimization problem, the input is a pair ( U , S ) {displaystyle ({mathcal {U}},{mathcal {S}})} , 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. 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 log ⁡ n {displaystyle scriptstyle log n} , so its relaxation gives a factor- log ⁡ n {displaystyle scriptstyle log n} approximation algorithm for the minimum set cover problem (where n {displaystyle scriptstyle n} is the size of the universe). In weighted set cover, the sets are assigned weights. Denote the weight of set S ∈ U {displaystyle Sin {mathcal {U}}} by w S {displaystyle w_{S}} . Then the integer linear program describing weighted set cover is identical to the one given above, except that the objective function to minimize is ∑ S ∈ S w S x S {displaystyle sum _{Sin {mathcal {S}}}w_{S}x_{S}} .