Chapter 6: Dynamic Programming
6.1 Weighted Interval Scheduling: A Recursive Procedure In the interval scheduling problem the goal of our algorithm was to accept as large a set of non-overlapping intervals as possible. This chapter looks at intervals with certain values or weights from which we want to find a set of maximum value. If we have n requests, with each request I specifying a start time and finish time. Each interval has a value, and two intervals are compatible if they don’t overlap. Our goal is to select a subset of mutually compatible intervals so that we maximize the sum of the values of the selected intervals. We also consider an optimal solution O where either the last interval n belongs to O or doesn’t. If n does belong to O, then no interval indexed between p(n) and n can belong to O, because we know those intervals all overlap interval n. If n does not belong to O, then O is equal to the optimal solution to the problem consisting of requests 1 to n-1. We can decide that n belongs to the optimal solution if and only if the first of the options is a least as good as the second (p. 254). This reflects one of the components of dynamic programming in that the recurrence equation that expresses the optimal solution in terms of the optimal solutions to smaller subproblems. The algorithm on p. 254-5 is a recursive algorithm that will copmute opt(n) given that the requests are sorted by finishing times and the values for each interval have been computed. This algorithm runs at exponential time in the worst case and we want to find a polynomial time solution. If we eliminate the redundancy of the number of recursive calls, we can reduce the running time. A way to take care of this would be to store the value of Compute-Opt in a globally accessible place the first time we compute it and then simply use this value in place of recursive calls, a method called memoization. The proof on p. 257 shows how memoization has brought the running time down to O(n). Once we have used M-Compute-Opt(n) to find the value of the optimal solution, we need to find a full optimal set of intervals. We extend M-Compute-Opt(n) to maintain an array that contains the optimal set of intervals. We keep the running time down on this part by not explicitly maintaining S, but instead recovering the optimal solution from values saved in the array M after the optimum value has been computed.
6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems This section designs an efficient algorithm that iterates over subproblems instead of computing the solutions recursively. Using an array helps us accomplish this: M9n) contains the value of the optimal solution on the full instance and Find-Solution can be used to trace back through M efficiently and return an optimal solution itself. We can directly compute the entries in M by an iterative algorithm rather than just using the memorized recursion. We do this by starting with M[0] = 0 and keep incrementing j, which the Iterative-Compute-Opt algorithm on p. 259 does. The book states that often algorithms designed around an iterative buildup of subproblems can be simpler to express, but there is also usually a memoized version that does the same thing. The subproblems must have three properties: 1.) There are only a polynomial number of subproblems, 2.) The solutions to the original problem can be easily computed from the solutions to the subproblems, 3.) There is a natural ordering on subproblems from “smallest” to “largest.”
6.3 Segmented Least Squares: Multi-way Choices This section looks at recurrence that involves “multiway choices,” meaning at each step we have a polynomial number of possibilities to consider for the structure of the optimal solution. The book uses the example of plotting a best fit line on a set of data points. When we try to find the best fit line we want to find the one with minimum error. This becomes difficult if it looks like the points fall along more than one line. So instead we consider an approach involving us to fit all points using the fewest lines possible—the Segmented Least Squares Problem. We want to use change detection to identify a few points in the sequence at which a discreet change occurs. Each segment is a subset of a set of contiguous x-coordinates. For each segment we compute the line minimizing the error with respect to the points in our set. The penalty of a partition is defined by two things: 1.) The number of segments into which we partition P, times a fixed, given multiplier C >0, 2.) For each segment, the error value of the optimal line through that segment. Our goal is to find a partition of minimum penalty. There are exponentially many possible partitions of a set, but we can make our algorithm run in polynomial time. We have a polynomial number of subproblems. Pages 264-5 outline an algorithm that from a polynomial number of subproblems builds up solutions to these using recurrence. Instead of looking for a subset of n items, we want to partition the n. The algorithm’s running time is O(n2).
6.4 Subset Sums and Knapsacks: Adding a Variable This section looks at another type of problem, in which we need to create a “richer” set of subproblems by adding a new variable to the recurrence underlying the dynamic program. In this problem, we have one machine that processes jobs and a set of n requests. We can only use the resource between time 0 and time W, and we want to process jobs so that the machine stays busy until W. This is the main idea of the Knapsack Problem, where each problem has a value and a weight and our goals is to select a subset of maximum total value whose weight does not exceed W. Our best solution comes from using a subset of the first n-1 items and the total allowed weight W – wn, so we need a subproblem for each initial set of {1 . . . i} items (see pages 268-9). This is a pseudo-polynomial problem, meaning it is a polynomial function of n and W, the largest integer involved in defining the problem. These types of problems are therefore more efficient for relatively small input.
