Minimum Set Cover Task

From GM-RKB
Jump to navigation Jump to search

A Minimum Set Cover Task is a combinatorial optimization task (with a set function) that is an minimization task used to find the smallest subset of sets that covers all elements in a given universe.



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.