I am trying to implement a solution for a set coverage problem using a greedy algorithm.
The classic greedy approximation algorithm for it is
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:
a. Will doing the algorithm in reverse be a valid 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 easy to get C and there will be a limited number (<5) of redundant sets - in this case will this removal algorithmm would perform better?
The algorithm will surely return a valid set cover as at every step it checks if all elements of s are redundant. Intuitively I feel that part b is true though I am unable to write a formal proof for it. Read chapter 2 of Vijay Vazirani as it might help do the analysis part.