Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter line 3 so that it would run until the size of C was equal to n, and change the logic in line 4 so that it would pick and remove vertices until the size of n. A vertex would be removed when the size of C doesn't equal to n but the cover is complete. I can't really think of any other way to do it. The real problem is that I'm not entirely sure how to make the algorithm run in exponential time like they are asking.
GREEDY-SET-COVER can return a number of different solutions, depending on how we break ties in line 4. Give a procedure BAD-SET-COVER-INSTANCE.n/ that returns an n-element instance of the set-covering problem for which, depending on how we break ties in line 4, GREEDY-SET-COVER can return a number of different solutions that is exponential in n.
X - some finite set
F - a family of subsets of X
C - cover being constructed
GREEDY-SET-COVER can return a number of different solutions, depending on how we break ties in line 4. Give a procedure BAD-SET-COVER-INSTANCE.n/ that returns an n-element instance of the set-covering problem for which, depending on how we break ties in line 4, GREEDY-SET-COVER can return a number of different solutions that is exponential in n.
GREEDY-SET-COVER(n)
1 U = X
2 C = ∅
3 while U != ∅
3a select an S ∈ F that maximizes |S ∩ U|
3b U = U - S
3c C = C ∪ {S}
4 return C
$X$ — some finite set
$F$ — a family of subsets of $X$
$C$ — cover being constructed
EDIT-
GREEDY-SET-COVER($n$)
1 let $U = X$
2 let $C = \varnothing$
3 while $U \ne \varnothing$
3a select an $S \in F$ that maximizes $\left|S \cap U\right|$
3b set $U = U \setminus S$
3c set $C = C \cup \{S\}$
4 return $C$
Could it be said that since the number of subsets a set has is 2^n$2^n$ and that in the worst case this algorithm will end up finding all of those subsets before settling on an n-instance set to return.?
