Point coverage problem

Question

Recently, I encountered this problem when testing: considering the set of points m (all on the x axis) and the set of n lines with ends [l, r] (again on the x axis), we find the minimal subset n such that all points are covered by a line. Prove that your solution always finds the smallest subset.

The algorithm I wrote for it was something like: (for example, strings are stored as arrays with the left endpoint at position 0 and right at position 1)

algorithm coverPoints(set[] m, set[][] n): chosenLines = [] while m is not empty: minX = min(m) bestLine = n[0] for i=1 to length of n: if n[i][0] <= minX and n[i][1] > bestLine[1] then bestLine = n[i] add bestLine to chosenLines for i=0 to length of m: if m[i] <= bestLine[1] then delete m[i] from m return chosenLines 

I'm just not sure if this always finds a minimal solution. This is a simple greedy algorithm, so my gut tells me that it is not, but one of my friends, who is much better than me, says that for this problem, a greedy algorithm like this always finds a minimal solution. In order to prove that mine always finds a minimal solution, I made a very manual wave proof in contradiction, when I made the assumption that this is probably not the case. I definitely forgot what I did.

If this is not a minimal solution, is there a way to do this in less than something like O (n!) Time?

thanks

Answer 1

Your greedy IS algorithm is correct. We can prove this by showing that ANY other coating can only be improved by replacing it with a cover created by your algorithm.

Let C be a valid coverage for a given input (not necessarily optimal), and S be a coverage according to your algorithm. Now consider the points p1, p2, ... pk, which are the minimum points that you deal with at each stage of the iteration. C coverage should also cover them all. Note that in C there is no segment spanning two of these points; otherwise your algorithm would select this segment! Therefore, | C | > = k. And what is the cost (number of segments) in your algorithm? | S | = k.

This completes the proof.

Two notes:

1) Implementation: The initialization of bestLine with n [0] is incorrect, because the loop may not be able to improve it, and n [0] does not necessarily include minX.

2) Actually this problem is a simplified version of the Set Cover problem. While the original is NP-complete, this change is polynomial.

Answer 2

Hint: First try to prove that your algorithm works for sets of size 0, 1, 2 ... and see if you can generalize this to create proof by induction.