1
$\begingroup$

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.

  • 1
    @Suresh, looks like I lied.2012-02-23

1 Answers 1

3

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]$.

  • 0
    Ah yes. it should have been [1/4-eps, 3/4+eps]2012-02-23