Minimum Set Cover Task
A Minimum Set Cover Task is a set cover task (with a set function) that is an minimization task.
- Example(s):
- Counter-Example(s):
- See: Set Cover, Maximum Coverage, Submodular Function, Vertex Cover, NP-Complete Task, NP-Hard, Decision Problem, Bipartite Neighborhood Function.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/set_cover_problem Retrieved:2015-1-26.
- 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 [math]\displaystyle{ \{1,2,...,m\} }[/math] (called the universe) and a set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] sets whose union equals the universe, the set cover problem is to identify the smallest subset of [math]\displaystyle{ S }[/math] whose union equals the universe. For example, consider the universe [math]\displaystyle{ U = \{1, 2, 3, 4, 5\} }[/math] and the set of sets [math]\displaystyle{ S = \{\{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\}\} }[/math]. Clearly the union of [math]\displaystyle{ S }[/math] is [math]\displaystyle{ U }[/math]. However, we can cover all of the elements with the following, smaller number of sets: [math]\displaystyle{ \{\{1, 2, 3\}, \{4, 5\}\} }[/math].
More formally, given a universe [math]\displaystyle{ \mathcal{U} }[/math] and a family [math]\displaystyle{ \mathcal{S} }[/math] of subsets of [math]\displaystyle{ \mathcal{U} }[/math],
a cover is a subfamily [math]\displaystyle{ \mathcal{C}\subseteq\mathcal{S} }[/math] of sets whose union is [math]\displaystyle{ \mathcal{U} }[/math]. In the set covering decision problem, the input is a pair [math]\displaystyle{ (\mathcal{U},\mathcal{S}) }[/math] and an integer [math]\displaystyle{ k }[/math]; the question is whether
there is a set covering of size [math]\displaystyle{ k }[/math] or less. In the set covering optimization problem, the input is a pair [math]\displaystyle{ (\mathcal{U},\mathcal{S}) }[/math], 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 .If each set is assigned a cost, it becomes a weighted set cover problem.
- The set covering problem (SCP) is a classical question in combinatorics, computer science and complexity theory.