Algorithims 2. Consider the \"Shortest Interval first\" greedy algorithm for the

Question

Algorithims

2. Consider the "Shortest Interval first" greedy algorithm for the Interval Scheduling problem. In this algorithm, we repeatedly pick a shortest interval to include in our solution and as usual when an interval I is picked, then I and any overlapping intervals still present are deleted. The algorithm breaks ties arbitrarily; in other words, if there are multiple shortest intervals present, the algorithms picks one arbitrarily (a) Show that this algorithm does not solve the Interval Scheduling problem. In other words, even though the algorithm returns a non-overlapping set of intervals, the set it returns need not be the largest possible set (b) Let A be the set of intervals returned by the algorithm for some input and let O be an optimal solution for this input. Prove that every interval in A overlaps at most two intervals in C Note: This is not a long proof, but requires care. (c) Consider an arbitrary input and let A be the set of intervals returned by the algorithm for this input and let O be an optimal solution for this input. Now for each interval z in O, charge S1 to an interval y in A that overlaps r. Note that y could be identical to z. Also, note that y has to exist; otherwise the greedy algorithm would have added r to the set A. Thus the number of dollars charged is exactly equal to |O|. Now answer the following questions: (i) what is the maximum number of dollars that an interval in A is charged? (ii) what does this tell us about the relative sizes of A and O? (Express your answer as an inequality connecting A and |Ol.), and (ii) what does this tell us about the "shortest interval first" algorithm being an approximation algorithm for Interval Scheduling?

Explanation / Answer

ANSWER

GIVEN BY

1)

The maximum figure of dollars that can algorithm in A can be charged is $1, as charging of dolor for an interval y in A depends on whether it is overlap with some interval x in O.

If it is overlapping, it will be discarded and dolor will be emotional otherwise not.

It is not dependent on the period of the interval. In any conditions, at the max.

Only $1 will be charged whenever there is overlap, otherwise nothing will be charged for that interval.

2)

It is clear that any set A of intervals return by algorithm will be optimal if A = O.

3)

But it is hard to prove that A = O, yet we can show that |A| = |O| for optimality of A. Hence |O| is the upper bound on size of A.

4)

Hence,

as far as relative sizes of A and B are worried we can say that (not depending whether A is optimal or not.):

|A| leq |O|

3)

"Shortest interval first" does not lead to optimal solution because it doesn't assurance that there won't be any overlap in time selection.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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