Chapter 6

Sometimes greedy algorithms do not provide fully correct solutions to a problem that we may be trying to solve. We are forced to resort to other approaches to designing algorithms–one such approach is dynamic programming. In dynamic programming, one implicitly explores the space of all possible solutions, by carefully decomposing things into a series of subproblems, and then building up correct solutions to larger and larger subproblems. We can think of dynamic programming as somewhat of a balance between brute force search and the divide and conquer approach.

We have seen a greedy algorithm that produces an optimal solution to the Interval Scheduling Problem, where the goal is to accept as large a set of nonoverlapping intervals as possible. The Weighted Interval Scheduling Problem is a strictly more general version, in which each interval has a certain value (or weight), and we want to accept a set of maximum value. However, the greedy algorithm that worked before (repeatedly choosing the interval that ends earliest) is no longer optimal in this more general setting.

We have n requests labelled 1, …, n, with each request i specifying a start time s_i and a finish time f_i. Each interval i now also has a value, or weight v_i. Two intervals are compatible if they do not overlap. The goal of our current problem is to select a subset of mutually compatible intervals, so as to maximize the sum of the values of the selected intervals. Let’s suppose that the requests are sorted in order of nondecreasing finish time. We’ll say a request i comes before a request j if i < j. We define p(j), for an interval j, to be the largest index i < j such that intervals i and j are disjoint (note: p(j) = 0 if no request i < j is disjoint from j).

Now, consider an optimal solution O to this problem. We can say, with certainty, that the interval n (the last one) either belongs to O, or it doesn't. If n belongs to O, then clearly no interval indexed strictly between p(n) and n can belong to O. On the other hand, if n does not belong to O, then O is simply the optimal solution to the problem consisting of the requests {1, …, n-1}.

Thus, for any value of j between 1 and n, let O_j denote the optimal solution to the problem consisting of the requests {1, …, j}, and let OPT(j) denote the value of the solution. Based on our reasoning earlier, we can say that:

OPT(j) = max(v_j + OPT(p(j)), OPT(j - 1))

As such, a request j belongs to an optimal solution to the set {1, 2, …, j} if and only if v_j + OPT(p(j)) ≥ OPT(j - 1).

We therefore have a very simple algorithm that solves the problem for us:

Compute-Opt (j):
   If j = 0 then
      Return 0
   Else
   Return max(v_j + Compute-Opt(p(j)), Compute-Opt(j-1))
   Endif

Unfortunately, this algorithm runs in exponential running time (as the tree of recursive calls/values gets bigger and bigger–total number of calls made to Compute-Opt on an instance will grow like the Fibonacci numbers, which increase exponentially).

A fundamental observation, which forms the second crucial component of a dynamic programming solution, is that our recursive algorithm Compute-Opt is really only solving n+1 different subproblems: Compute-0pt(0), Compute-Opt(1), …, Compute-0pt(n). The fact that it runs in exponential time is simply due to the redundancy in the number of times it issues each of these calls. We could store the value of Compute-0pt in a globally accessible place the first time we compute it and then simply use this precomputed value in place of all future recursive calls in order to drastically improve the runtime. This is called memoization.