Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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($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$ 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?

share|improve this question
1  
I'm having a hard time understanding what you are asking. You are looking for an algorithm to... do what, exactly? What are the requirements? It's not clear what you are asking for. Are you asking for an exhaustive search algorithm to find the optimal set cover? (If so, the best way to do that is probably not to modify the algorithm you showed us, but rather to start from scratch.) Would this be clear to you, if you were reading it? I suggest you proofread the question and edit it to try to explain more clearly what you want to achieve and what you've already tried. –  D.W. Nov 24 '13 at 5:28
1  
you want the algo to run in exponential time?? –  Subhayan Nov 24 '13 at 9:01
    
@D.W. sorry for the confusion. My understanding of the problem wasnt thatvgreat to begin with. After some debate wiyh friends we've settled. On the idea thar they are asking for a set cover that has n elements in it. What really confused me about the question was that the last part about greedy set cover begin capable of returning an exponential amount of solutions. I wasn't sure why that was there. I'll that y to reorder and neaten everything up. –  thad Nov 25 '13 at 11:02
    
@Subhayan I thought that's what they were asking for but now i think it's more of a statement about the algorithm they wanted me to edit. –  thad Nov 25 '13 at 11:04
    
Please edit to make the algorithm unambiguous. For example, is line 6 a part of the while loop? –  David Richerby Nov 26 '13 at 17:08
show 1 more comment

1 Answer

I think you are being confused by the way the question is phrased. The question asks for a sequence of instances $I_n$, consisting of triples $\langle X_n,F_n \rangle$, such that $|X_n| = n$ and GREEDY-SET-COVER$(X_n,F_n)$ could have $C^n$ many results, for some constant $C>1$. These results come from the fact that at step 4 there could be many sets that are eligible.

For some reason, the question asks you for an algorithm which generates the sequence: given $n$, it should output $\langle X_n,F_n \rangle$. Since the instances you are going to construct will be pretty simple, you should have no problem writing an algorithm that generates them, but in fact no one cares about this algorithm; the point is only that these "bad" instances exist (they're not actually bad, mind you).

The easiest way to construct these instances is to use a gadget, say $F_3 = \{(1,2),(1,3),(2,3)\}$. You can check that running the greedy algorithm can result in three different covers. I'll let you continue from here.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.