Hi,

I am trying to understand the set cover problem. I found the algorithm at:

https://.mit.edu/~goemans/18434S06/setcover-tamara.pdf

I found the example:

Somebody please guide me how we evaluate the denominator |S-C|?

 

Zulfi.

Edited May 10, 20205 yr by zak100

Hi,

I received a response at:

https://math.stackexchange.com/questions/3668486/set-cover-problem-how-to-calculate-the-denominator

I have following questions:

(1)Why start with Z, cost is 7, cost of X is 6, we have to choose the least cost effective? (2) How are we choosing the denominators? In case of Z, denominators are 7, 5, 5, Z has 7 dots (or cardinality) but 5 are shareable and 2 are non-shareable? X has 5 shareable dots, 2 shared with Z and 3 shared with Y, denominators are 3 and 5 how?, Y has 5 elements 3 shareable with X and 2 non-shareable, denominator is 2, why? (3) What is the purpose of these 3 rounds? (4) What is the answer of set Cover? Example says optimal cost is 22? What is the cost in case of greedy algorithm?

Somebody please guide me.

 

Zulfi