Consider the following greedy algorithm for the interval scheduling problem: Pic

Question

Consider the following greedy algorithm for the interval scheduling problem: Pick an interval I with minimum length, remove I and all intervals that overlap with I, and repeat this process until no more intervals remain. The pseudocode for the algorithm is described as follows (Note: S is the set of input intervals):

Set R to S, and 0 to the empty set.

While R is not empty {

Let i be an interval in R with minimum length. (Break ties arbitrarily)

Add i to 0.

Remove from R interval i and all intervals that conflict with i.

} endwhile

Return 0.

A. Give an example that shows this algorithm does not always return an optimal solution. (10 points) B. Is it true that on every input instance the solution returned by the algorithm has a size that is at least half the size of an optimal solution? Provide an argument supporting your answer. (20 points)

Explanation / Answer

(a)Here is the example -

1_______________________1 2________________________2

3__________3

Here is the example where its shows that greedy approach doesn't work for minimum length interval.Here minimum length interval is 3________3 but this not the solution instead of it 1___________________1 and 2________________2 are better solution and we can combine them too.

(b) Yes, this is true for this Algorithm.

Let's understand with an example for the above mentioned algoorithm.

1_______1 2__________2 3_____________3 4_________________4

5____________5 6_______6 7__________________7

Here based on this algorithm we get 1_____1 6_____6 4_______________4 7______________7 as solution.

But optimal solution is 1____1 2___________2 3_____________3 4____________4 7_________________7.

So we can see that we can get at least half of the size of optimal solution on each input instance .

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.