Minimum Set Cover Task

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.

• Context:
  • It can be solved by a Minimum Set Cover Solution System (that implements a minimum set cover solving algorithm, possibly a greedy algorithm due to its NP-completeness).
  • ...
  • It can range from being a Weighted Set Cover Task to being a Unweighted Set Cover Task.
  • ...
  • It can be applied in areas such as sensor placement, where the task is to cover a region with the minimum number of sensors.
  • It is closely related to the hitting set problem, which is its dual formulation.
  • ...
• Example(s):
  • a Minimal Biclique Set Cover Task.
  • a real-world application in wireless network coverage, where the task is to place the minimum number of access points to cover all users.
  • an example in data mining for covering all necessary features with the smallest number of representative subsets.
  • …
• Counter-Example(s):
  • a Minimum Set Packing Task, where the objective is to select the maximum number of disjoint sets.
  • a Minimum Vertex Covering Task, which focuses on covering all edges in a graph with the smallest number of vertices.
  • a Minimum Edge Covering Task, which aims to cover all vertices in a graph using the fewest edges.
• 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.

---