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:
“And the sentinel stars set their watch in the sky;”
—Thomas Campbell (1774–1844)
“When you are listening to music it is better to cover your eyes than your ears.”
—José Bergamín (1895–1983)
“A serious problem in America is the gap between academe and the mass media, which is our culture. Professors of humanities, with all their leftist fantasies, have little direct knowledge of American life and no impact whatever on public policy.”
—Camille Paglia (b. 1947)