Set Cover Problem
The set covering problem (SCP) is a classical question in combinatorics, computer science and complexity theory. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms. It was also one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the universe) and sets whose union comprises the universe, the set cover problem is to identify the smallest number of sets whose union still contains all elements in the universe. For example, assume we are given the following elements and sets . Clearly the union of all the sets in contain all elements in . 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 version of set cover is NP-hard.
| Covering-packing dualities | |
| Covering problems | Packing problems |
|---|---|
| Minimum set cover | Maximum set packing |
| Minimum vertex cover | Maximum matching |
| Minimum edge cover | Maximum independent set |
Read more about Set Cover Problem: Integer Linear Program Formulation, Hitting Set Formulation, Greedy Algorithm, Low-frequency Systems, Inapproximability Results, Related Problems
Famous quotes containing the words set, cover and/or problem:
“Racism is when you have laws set up, systematically put in a way to keep people from advancing, to stop the advancement of a people. Black people have never had the power to enforce racism, and so this is something that white America is going to have to work out themselves. If they decide they want to stop it, curtail it, or to do the right thing ... then it will be done, but not until then.”
—Spike Lee (b. 1956)
“If I use the media, even with tricks, to publicise a black youth being shot in the back in Teaneck, New Jersey ... then I should be praised for it, and it’s more of a comment on them than me that it would take tricks to make them cover the loss of life.”
—Al, Rev. Sharpton (b. 1954)
“What happened at Hiroshima was not only that a scientific breakthrough ... had occurred and that a great part of the population of a city had been burned to death, but that the problem of the relation of the triumphs of modern science to the human purposes of man had been explicitly defined.”
—Archibald MacLeish (1892–1982)