Mahmoud Kamal
Idea: “You must select a minimum number [of any size set] of these sets so that the sets you have picked contain all the elements that are contained in any of the sets in the input.” Additionally, you want to minimize the cost of the sets.
Input:
Universe U={A,B,C,…,Z} Subsets S=S1,S2,S3,..Sk ⊆ UCosts C= C1,C2,…Ck
Goal: Find a set I ⊆ S minimize ∑C, such that (∪ S)=U
Algorithm:
We used to solve this problem the greedy- method.
Let C represent the set of elements covered so far
Let cost effectiveness, or α, be the average cost per newly covered node
Algorithm:
1. C ← 0
2. While C ≠ U do
Find the set whose cost effectiveness is smallest, say S
Let
For each e∈ S-C, set price(e) = α
C ← C ∪ S
3. Output picked sets (note: the greedy algorithm is not optimal. )
Programming Languages:
1) python
2) Haskell
3)JavaScript .
