Clever Geek Handbook

Greedy Set Coverage algorithm built with * remove * sets

I am trying to implement a solution for a set spanning problem using a greedy algorithm.

The classic greedy approximation algorithm for it

input: collection C  of sets over universe U  , costs: Cā†’R ā‰„0    
output: set cover S   
1. Let Sā†āˆ….  
2. Repeat until S covers all elements:  
3.   Add a set s to S, where sāˆˆC maximizes the number of elements in s not yet covered by set s in S, divided by the cost c(s). 
4. Return S.

I have a question in 2 parts:

and. Executing the algorithm in reverse order is the correct algorithm, i.e.

input: collection C  of sets over universe U  , costs: Cā†’R ā‰„0    
output: set cover S   
1. Let Sā†C  .  
2. Repeat until there are no sāˆˆS such that S-s=S (i.e. all elements in s are redundant):  
3.   Remove a set s from S, where sāˆˆS minimises the number of elements in s, divided by the cost c(s). 
4. Return S.

b. The nature of the problem is such that it is easy to obtain C and there will be a limited number (<5) of redundant sets - in which case, will this removal algorithm perform better?

+3


source to share


1 answer


The algorithm will surely return a valid set, as in each step that checks if all elements of s are redundant. Intuitively I feel that part b is true, although I cannot write a formal proof for it. Read chapter 2 of Vijay Vazirani as it can help do some of the analysis.



+1


source






More articles:


All Articles