Proof of optimality of greedy algorithm for scheduling

user_7054698 0
Viewed 48

Unable to come up with a formal proof of optimality for algorithm A for the given problem. Have convinced myself that it is possible to execute some optimal schedule O in increasing order of the events' deadline. But don't know how to formally prove that extract_max operation converges to an optimal solution.

Problem

: Given a list of events with deadline date 'd' and duration 'l' days, provide algorithm to select events such that maximum number of them can be chosen. Of course, each event must be scheduled such that it finishes by deadline date 'd', it must run continuously for its duration 'l' days, and only one event can run at any given time.

**Greedy Algorithm A:**

Create max_heap S  //schedule

Sort events by their deadline (increasing).

for(j=0;j<events.size();j++)

{ 

  If you can incorporate event j into schedule S, do so. 

  Else, if(longest event in S > length of j) swap it with j. 


}

Return S; 

END
greedy proof scheduling optimization algorithm
1 Answers

We can prove this by contradiction. Assume that the greedy choice were not part of the optimal solution; that is, if we consider the tasks sorted in ascending order of deadline, the optimal solution wouldn't include the one with the earliest deadline. Now, consider the task with earliest deadline in any hypothetical optimal solution. Either it overlaps with the greedy choice (in which case we might as well have chosen the greedy choice, since it finishes no later than the earliest task in the optimal solution, and cannot overlap with any earlier tasks in the optimal solution, since it was the earliest task); or else it doesn't overlap, in which case the optimal solution wasn't optimal (since we could also freely have included the greedy choice in it). In both cases, we have a contradiction (in the first, that the greedy solution couldn't have been picked; in the second, that the solution without the greedy choice was optimal) and so the assumption that the optimal choice doesn't contain the greedy choice was wrong; the optimal solution does include the greedy choice.

user_8472690
Related