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.

Say we aim to build a connected communication network, using a set of locations V = {v₁, …v_n}, as cheaply as possible. A link between pairs has a certain cost, so each edge e has a particular cost c_e. If T is a minimum-cost solution to this problem, then (V, T) is a tree. Because of this, we can rephrase the goal of this problem as finding the cheapest spanning tree of the graph, where subset T ⊆ E is a spanning tree of G if (V, T) is a tree. Hence, we call this problem the Minimum Spanning Tree Problem.

There are three greedy algorithms which can be used to solve this problem: Kruskal's Algorithm, Prim's Algorithm, and the Reverse-Delete Algorithm. Each algorithm works by repeatedly inserting or deleting edges from a partial solution. There are two important properties which need to be defined in order to analyze these algorithms: the Cut Property and the Cycle Property. The Cut Property says the following, and allows us to know when it is safe to include an edge in the minimum spanning tree:

  Assume that all edge costs are distinct. Let S be any subset of nodes that is neither empty nor equal to all of V, and let edge e = (v, w) be the minimum-cost edge with one end in S and the other in V - S. Then every minimum spanning tree contains the edge e.

We can use the Cut Property to prove that Kruskal's Algorithm and Prim's Algorithm both produce optimal solutions for the minimum spanning tree of G. The Cycle Property says the following, and allows us to know an edge is not in the minimum spanning tree:

  Assume that all edge costs are distinct. Let C be any cycle in G, and let edge e = (v, w) be the most expensive edge belonging to C. Then e does not belong to any minimum spanning tree of G.

The Cycle Property is used to prove the optimality of the Reverse-Delete Algorithm. I understood this section alright. I would have liked to understand more simply how to Cycle and Cut Properties are implemented to show these things, because the way the book tried to explain this was unclear. I would rate it a 6.