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:
“The dreariest spot in all the land
To Death they set apart;
With scanty grace from Nature’s hand,
And none from that of Art.”
—John Greenleaf Whittier (1807–1892)
“He is a stranger to me but he is a most remarkable man—and I am the other one. Between us, we cover all knowledge; he knows all that can be known and I know the rest”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“Theology, I am persuaded, derives its initial impulse from a religious wavering; for there is quite as much, or more, that is mysterious and calculated to awaken scientific curiosity in the intercourse with God, and it [is] a problem quite analogous to that of theology.”
—Charles Sanders Peirce (1839–1914)