How should I approach this question? I am stuck and don't even know what a weighted set cover is.

 

 

2. (*** level) Weighted Set Cover In class (and Chapter 5.4) we looked at a greedy algorithm to solve the set cover problem, and proved that
if the optimal set cover has size k, then our greedy algorithm will find a set cover of size at most klogn. Here is a generalization of the set cover problem. - Input: A set of elements B of size n; sets 51,. . . ,5", g B; positive weights w1,. . . , Wm.
' Output: A selection of the sets S,- whose union is B. - Cost: The sum of the weights w; for the sets that were picked. Design an algorithm to find the set cover with approximately the smallest cost. Prove that if there is a
solution with cost k, then your algorithm will find a solution with cost 0(klog n). Please provide the Main
Idea and Proof of Correctness only. If you think Pseudocode can better convey your idea, add it to the Main
Idea. Note: We will accept solutions whose running time is a reasonable (low-order) polynomial in n and m. Do
not expend too much effort trying to get the running time as low as possible; we are much more concerned with achieving the required approximation factor.

Attachments:

• 1493342028-Screen Shot 2017-03-07 at 9.48.43 AM.png