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:
“What is love itself,
Even though it be the lightest of light love,
But dreams that hurry from beyond the world
To make low laughter more than meat and drink,
Though it but set us sighing?”
—William Butler Yeats (1865–1939)
“I wouldn’t pray just for a old man that’s dead because he’s all right. If I was to pray, I’d pray for the folks that’s alive and don’t know which way to turn. Grampa here, he ain’t got no more trouble like that. He’s got his job all cut out for him. So cover him up and let him get to it.”
—Nunnally Johnson (1897–1977)
“The problem for the King is just how strict
The lack of liberty, the squeeze of the law
And discipline should be in school and state....”
—Robert Frost (1874–1963)