Lesson plan

Set cover problem

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. Given a set of elements (henceforth referred to as the universe, specifying all possible elements under consideration) and a collection, referred to as , of a given subsets whose union equals the universe, the set cover problem is to identify a smallest sub-collection of whose union equals the universe. For example, consider the universe, and the collection of sets {{math|1=S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }.}} In this example, is equal to 4, as there are four subsets that comprise this collection. The union of is equal to . However, we can cover all elements with only two sets: {{math|{ {1, 2, 3}, {4, 5} }‍}}, but not with only one set. Therefore, the solution to the set cover problem for this and has size 2. This example is illustrated in the picture above. More formally, given a universe \mathcal{U} and a family \mathcal{S} of subsets of \mathcal{U} , a set cover is a subfamily \mathcal{C}\subseteq\mathcal{S} of sets whose union is \mathcal{U} . * In the set cover decision problem, the input is a pair (\mathcal{U},\mathcal{S}) and an integer k ; the question is whether there is a set cover of size k or less.…

Back to article

Article summary

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. Given a set of elements (henceforth referred to as the universe, specifying all possible elements under consideration) and a collection, referred to as , of a given subsets whose union equals the universe, the set cover problem is to identify a smallest sub-collection of whose union equals the universe. For example, consider the universe, and the collection of sets {{math|1=S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }.}} In this example, is equal to 4, as there are four subsets that comprise this collection. The union of is equal to . However, we can cover all elements with only two sets: {{math|{ {1, 2, 3}, {4, 5} }‍}}, but not with only one set. Therefore, the solution to the set cover problem for this and has size 2. This example is illustrated in the picture above. More formally, given a universe \mathcal{U} and a family \mathcal{S} of subsets of \mathcal{U} , a set cover is a subfamily \mathcal{C}\subseteq\mathcal{S} of sets whose union is \mathcal{U} . * In the set cover decision problem, the input is a pair (\mathcal{U},\mathcal{S}) and an integer k ; the question is whether there is a set cover of size k or less.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.