Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I'm covering the interval [0,1] with sets which are themselves closed intervals, is there a covering where the greedy algorithm does not find the optimal solution?

If the sets are not individual closed intervals (assume there are not open intervals) I can construct an example by letting one of the sets be two disconnected intervals; but I'm looking for an easier example for a presentation to a non-mathematical audience.

share|improve this question
1  
It is not clear what you mean by "optimal solution". Indeed, it is not clear what you mean by "solution", since it is not clear what problem your algorithm is trying to solve. And, at the risk of piling on, it is not clear what the "greedy algorithm" is, in this context. Please edit your question so others can know what you have in mind. –  Gerry Myerson Feb 22 '12 at 23:27
    
the set cover problem is a classic NP complete problem, one of the problems off of Karp's list. –  Michael Conlen Feb 23 '12 at 2:58
    
So, Michael, are you interested in getting answers to your question, or aren't you? If you are, meet us halfway, give us something to go on, explain what problem you are trying to solve, what algorithm you are using to solve it, what makes a solution optimal, etc. If you're not interested in getting answers, you're doing just fine, keep up the good work. –  Gerry Myerson Feb 23 '12 at 6:17
    
I think the OP wants to know if the greedy algorithm will fail to obtain the smallest cardinality set of intervals that covers the interval. Here the greedy algorithm is probably the one where you pick the interval that has maximum intersection with the as yet uncovered portion –  Suresh Venkat Feb 23 '12 at 8:54
1  
@Suresh, looks like I lied. –  Gerry Myerson Feb 23 '12 at 11:28
show 1 more comment

1 Answer

Assuming that Suresh is guessing correctly,

There are simple examples involving just three sets, where only two of the three sets are needed to get a cover, but the greedy algorithm uses all three.

EDIT: Just to incorporate in the answer what's already in the comments, one simple example consists of the three sets, $[0,1/2]$, $[1/2,1]$, and $[1/5,4/5]$.

share|improve this answer
    
Specifically, consider the set [0, 0.5], [0.5, 1], [1/3, 2/3]. Greedy will pick the last set and then will be forced to pick the other two. A better greedy algorithm is to pick greedily starting from 0. I believe that will yield the optimal solution. –  Suresh Venkat Feb 23 '12 at 17:37
    
@Suresh, the last of your three sets is shorter than the other two, so if "greedy" means what I think it means then a greedy algorithm will not pick the last set. Of course OP will not find it difficult to modify the example you have given. –  Gerry Myerson Feb 23 '12 at 22:15
    
@Suresh, starting from zero can fail if there are infinitely many sets. If the sets are $[0,0]$ and $[1/(n+1),1/n]$ for $n=1,2,\dots$, then greedy starting at zero picks $[0,0]$ and spins its wheels forever, unable to make another choice. –  Gerry Myerson Feb 23 '12 at 22:23
    
Ah yes. it should have been [1/4-eps, 3/4+eps] –  Suresh Venkat Feb 23 '12 at 22:51
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.