Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Set cover problem
Summary
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 {1, 2, ..., n} (called the universe) and a collection S of m sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of S whose union equals the universe. For example, consider the universe U = {1, 2, 3, 4, 5} and the collection of sets S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: { {1, 2, 3}, {4, 5} }.
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.
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 . It has been shown that its relaxation indeed 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 .
Set covering is equivalent to the hitting set problem.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.