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:
“When you have come into the land that the LORD your God is giving you, and have taken possession of it and settled in it, and you say, “I will set a king over me, like all the nations that are around me,” you may indeed set over you a king whom the LORD your God will choose. One of your own community you may set as king over you; you are not permitted to put a foreigner over you, who is not of your own community.”
—Bible: Hebrew, Deuteronomy 17:14,15.
“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)
“The problem of the twentieth century is the problem of the color-line—the relation of the darker to the lighter races of men in Asia and Africa, in America and the islands of the sea. It was a phase of this problem that caused the Civil War.”
—W.E.B. (William Edward Burghardt)