Chapter 4: Greedy Algorithms

In the interval scheduling problem, we considered a set of requests {1, 2, …, n} where the i^th request corresponds to an interval of time beginning at s(i) and finishing at f(i). A subset of the requests is compatible if no two of them overlap in time. We would like to maximize the compatible subset, which would be the optimal subset. A greedy algorithm for interval scheduling could be designed as follows:

  Initially let R be the set of requests and let A be empty
  While R is not empty
      Choose a request i ∈ R that has the smallest finishing time
      Add request i to A
      Delete all requests from R that are not compatible with request i
  Endwhile
  Return set A as the set of accepted requests

We want to prove that this solution is optimal, and we know that A is a compatible set of requests. To prove that greedy “stays ahead” we will set O to be the optimal set of intervals, and we want to show that A contains the same number of intervals as O. If we let i₁, …, i_k be the set of requests in A in the order they were added to A and j₁, …, j_m be the set of requests in O in the order they were added to O, then we want to prove that k = m. Using induction, we can prove that for all indices r ≤ k, f(i_r) ≤ f(j_r). Because of this, we know that for each r, the r^th interval finishes at least at the same time, if not earlier, than the r^th interval in O. The running time of this algorithm is O(nlogn).

There are many variations and extensions of the Interval Scheduling Problem, for example the Interval Partitioning Problem, where there are many identical resources which we must schedule all the requests to use as few of as possible. The algorithm for this problem is seen here:

  Sort the intervals by start times, breaking ties arbitrarily
  Let I1, ..., In denote intervals in this order
  For j = 1, 2, 3, ..., n
      For each interval Ii that precedes Ij in sorted order and overlaps it
          Exclude the label of Ii from consideration for Ij
      Endfor
      If there is any label from {1, 2, 3, ..., d} that has not been excluded then
          Assign a nonexcluded label to Ij
      Else leave Ij unlabeled
  Endfor
  

This section was very clear and understandable since we have covered it in class already. We followed the logic that the book followed so it was clear what was going on while I was reading. I would rate this section a 9 for readability.

Given a single resource and a set of n requests to use the resource for an interval of time, with each request having a specific deadline, we want to find a way to minimize the lateness, which results from missed or delayed deadlines. This algorithm differs from the algorithms seen in 4.1 since we must find a start and finish time for each request. To find the optimal solution for this problem, we organize the requests by Earliest Deadline First, or in an increasing order of the jobs' deadlines. Here is the algorithm:

  Order jobs by their deadlines
  Assume d1 ≤ ... ≤ dn
  Initially, f = s
  Consider the jobs i = 1, 2, ..., n in this order
      Assign job i to the time interval from s(i) = f to f(i) = f + ti
      Let f = f + ti
  End
  Return the set of scheduled intervals [s(i), f(i)] for i = 1, 2, ..., n
  

We would like to prove that this algorithm produces an optimal schedule. Rather than use a proof that greedy stays ahead, we will modify O, the optimal solution, while preserving its optimality, to make it identical to our solution A. This is called the exchange argument. To do this, we must declare that A' has an inversion if a job i with deadline d_i is scheduled before another job j with earlier deadline d_j < d_i. We know that our schedule A produced by the above algorithm has no inversions, and we can prove that all schedules with no inversions and no idle time have the same maximum lateness. To prove our algorithm's optimality, we simply must show that there is an optimal schedule with no inversions and no idle time by finding an optimal schedule with no idle time and converting it into a schedule with no inversions:

1. If O has an inversion, then there is a pair of jobs i and j such that j is scheduled immediately after i and has dj < di
2. After swapping i and j we get a schedule with one less inversion
3. The new swapped schedule has a maximum lateness no larger than that of O

Therefore, since A and O are schedules with no idle time and no inversions, the schedule we got from the greedy algorithm is optimal.

This section was confusing for me. I understand what we are trying to argue (that A is optimal) and how we are trying to argue it (by adjusting O so that it is the same as A) but I struggle to understand how we can claim that if a schedule has no idle time or inversions then it is optimal. I do not think that the book explained this section very well, though it is clearer to me now than it was during class. I would rate it a 6.5.

We can apply greedy algorithm practices to graphs in order to find the shortest paths in graphs. When looking at graphs, it can be helpful to know what the shortest path between two given nodes is or what the shortest path from a given node to all other nodes is. Dijkstra's Algorithm, shown below, can be used to solve these problems. Note that d'(v) = min_{e=(u,v):u∈S}d(u) = l_e.

  Dijkstra's Algorithm(G, l)
  Let S be the set of explored nodes
      For each u ∈ S, store a distance d(u)
  Initially S = {s} and d(s) = 0
  While S ≠ V
      Select a node v not in S with at least one edge from S for which d'(v) is as small as possible
      Add v to S and define d(v) = d'(v)
  Endwhile

We can use the greedy stays ahead method to prove the correctness of this algorithm. If implemented using a priority queue, Dijkstra's Algorithm can run in O(mlogn) time.