Chapter 4 - Greedy Algorithms

The section begins by bringing back a problem from earlier in the text: the Interval Scheduling Problem. In this problem, we are given a set of requests with start and finish times, and we are asked to find the largest subset of requests such that none of the times overlap. We want to devise a greedy algorithm to solve this problem.

The book walks through the different strategies we could use: ordering by start times, total time intervals, basing intervals on other intervals, and finally, finish times. It turns out that by ordering the requests by finish times, we have a greedy algorithm that matches the optimal solution.

The algorithm begins with a while loop on the set of all requests R. It says that while that set is nonempty, we choose the request with the smallest finishing time, we add that request to our set A (which will contain the solution), and then delete all requests from R that are not compatible with the request we just added to A. This algorithm is intuitive, and the book walks through the proof behind it well. Finally, the text diagnoses the runtime of the algorithm which is O(nlogn). Note that the runtime here is caused by ordering the finish times in sorted order, which we know takes O(nlogn) time.

Next, the book moves on to a similar problem. Here, we are given another set of requests, and we wish to schedule all of these requests using as few resources as possible. The book provides a good example to contextualize this using the idea that if we are given a set of class times, how many classrooms will we need to accommodate these class times. The text proves the intuitive fact that the number of resources needed is at least the depth of the set of intervals.

The algorithm follows similarly from the algorithm produced earlier in the section. First, we sort the intervals by their start times. As we progress through these sorted intervals j = 1,2,…,n, for any two intervals that are overlapping, we exclude the label from the preceding (earlier) interval I_i from consideration with the later interval I_j (in the same resource). And then if there is a label that has not been excluded during this call of the for loop, we assign a nonexcluded label to I_j. If there does not exist such a label, we leave I_j unlabeled.

The book does not diagnose the runtime of this algorithm. However, it does analyze the algorithm, ultimately concluding that the algorithm will schedule every interval on a resource, using a number of resources equal to to the depth, which was not as clear before reading the section carefully.

This section was long, and hard to follow at times. I would rate the readability at 5/10.

This section begins by slightly manipulating the interval scheduling problem such that each request is given a time t and a deadline d. Our goal is to minimize the maximum lateness of the requests. The text walks through a few different strategies for solving this problem. It spends some time attacking the strategy of ordering by the amount of time each request takes and the strategy of ordering by slack time (d - t). It then concludes that the clear choice to produce an optimal solution is ordering by increasing deadlines. The text then walks through an algorithm will it claims will accomplish this.

The algorithm first orders the jobs in order of their deadlines. It then considers each job in this sequence, creates a start and finish time for each job by using the information given, and returns the set of scheduled intervals after conducting this loop.

It then walks through the long and dwindling proof that this solution is indeed optimal. It does this by using an exchange argument. The exchange argument is used by defining something called an inversion. An inversion is a pair of jobs i and j such that j is scheduled immediately after i and has d(j)<d(i). The text takes an optimal schedule, supposes it has inversions, and then shows by eliminating these inversions, we still have an optimal schedule (minimizing maximum lateness) which is identical to the schedule which is created by the algorithm. We know this because the algorithm produces a schedule with no inversions.

I would rate the readability of this section at 8/10. It was interesting and a helpful supplement to what we learned in class.