Minimal Covering Set: System of Distinct Representatives

  • A
  • Thread starter WWGD
  • Start date
  • Tags
    Set
In summary, a minimal covering set is a set of elements that covers all the elements of another set with the minimum number of elements possible. It is used in solving problems related to set theory, combinatorics, and scheduling. The calculation of a minimal covering set involves finding a system of distinct representatives using algorithms such as the greedy algorithm, the branch-and-bound method, or the linear programming method. Minimal covering sets have applications in mathematics, computer science, operations research, and real-world fields such as logistics and supply chain management.
  • #1
WWGD
Science Advisor
Gold Member
7,032
10,618
Hi All,
Let ##s: \{s_1,s_2,...,s_j \}## be a collection of elements contained in the sets ##S:=\{S_1,S_2,...S_k \}## , no relation between ##j,k##; a given ##s_i## may be contained in one or more ##S_n##. I want to find a minimal "cover" for ##s##, i.e., the smallest subcollection of sets in ##S## that contains every element in ##s##. I think this is called an SDR : System of Distinct Representatives.
Is there a general formula dealing with this? Obviously, ##k## is an upper bound.
 
Physics news on Phys.org
  • #2
  • Like
Likes WWGD

Related to Minimal Covering Set: System of Distinct Representatives

What is a minimal covering set?

A minimal covering set is a set of elements that covers all the elements of another set with the minimum number of elements possible. In other words, it is the smallest set that contains at least one element from each subset of a larger set.

What is a system of distinct representatives?

A system of distinct representatives is a collection of elements that are chosen from different sets in a way that each element is unique and no two elements are chosen from the same set. This system is used to solve problems related to finding a minimal covering set.

What is the significance of a minimal covering set?

A minimal covering set is significant because it helps in solving various problems related to set theory, combinatorics, and scheduling. It is used in tasks such as scheduling exams, assigning tasks to workers, and creating tournament schedules.

How is a minimal covering set calculated?

The calculation of a minimal covering set involves finding a system of distinct representatives for a given set. This can be done using various algorithms such as the greedy algorithm, the branch-and-bound method, or the linear programming method.

What are the applications of minimal covering sets?

Minimal covering sets have various applications in mathematics, computer science, and operations research. They are used in scheduling problems, database design, graph theory, and network flow optimization. They also have real-world applications in fields like logistics, transportation, and supply chain management.

Similar threads

"Minimal Cover" in Finite Collection of Sets?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
972
I When does ## { n \choose k } ## represent set of lists?
    • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
A proof that a union of compact spaces is compact
    • Calculus and Beyond Homework Help
Replies
12
Views
1K
I Enumerating a Large Ordinal: Can We Find a Limit to the Continuum?
    • Set Theory, Logic, Probability, Statistics
Replies
27
Views
3K
MHB An open cover is a collection of open sets whose union contains a given subset
    • Topology and Analysis
Replies
16
Views
2K
B Proving half of the Heine-Borel theorem
    • Calculus
Replies
3
Views
1K
Is coutnable unions of finite sets an infinite set?
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
6K
MHB Solving a system of an arbitrary number of ODEs, at steady-state
    • Differential Equations
Replies
1
Views
1K
Is the Number of Binary Sequences Countable or Uncountable?
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
3K
Solve Set Theory Question: Family of Subsets F of {1,2,..k}
    • Calculus and Beyond Homework Help
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top