Dynamic Programming

As has already become prevalent in our brief class discussions, dynamic programming feels very much like we are tiptoeing around brute force exploration. The technique consists of breaking the search space into smaller subproblems, and then growing progressively larger until we have a global solution. An important key to note is that these techniques are crucial to problems for which greedy algorithms do not exist, especially because our thus far studied divide and conquer algorithms are relatively weak in that they primarily can only increase the speed of already-polynomial size problems–they can very rarely reduce exponential to polynomial time.

The weighted interval scheduling problem is a generalization of the standard interval scheduling problem for which we found a simple greedy solution. This takes a set of intervals which have weights and works to maximize the total weight. The “standard” version of the problem was simply that in which the weights were all 1, and counterexamples are easily developed to show that the old greedy algorithm does not work if weights can be different.

First, we suppose we have n requests labeled 1,…,n, where each request has a value or weight v_i and start and finish times s_i, f_i. Suppose that we have the requests already sorted by ascending finish times–yielding the same natural order based on finish times as we've used previously.

Additionally, we define for an interval j, p(j) is the largest index i<j such that the intervals i and j are disjoint–not overlapping. Also, p(j)=0 if there is no request before j that is disjoint with it.

Thus, we can consider some optimal solution O in the abstract, and we know that for every interval j , either O includes j or it does not. So, we can consider the optimal solution of all subproblems consisting of requests {1,…,j} for all j up to n. Then, letting OPT(j) denote the value of each of those solutions, we see that:

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

That is, either the optimal solution up to j includes j, in which case the optimal value is the value of j plus the optimal value of the problem of all the indices which fit below j, OR the optimal solution does not include j, in which case the optimal value is that of the problem up to j-1. Taking the max of these guarantees we stick with the greatest value as we move upwards to j=n. We say that j is included in the optimal solution on set {1,…,j} if and only if the first term in the above equation is greater than or equal to the second.

Unfortunately, if we simply run through this for all j from 1 to n, then we end up computing the same values over and over again. This can be solved by memoizing the solutions of already computed OPT values in an array M of size n. So, the final algorithm looks like:

M-Compute-Opt(j):

• If j=0:
  • return 0
• Else if M[j] is not empty:
  • return M[j]
• Else:
  • Define M[j] = max(v_j + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
    • return M[j]

Assuming the intervals are already sorted by end times, this algorithm runs in linear O(n) time.

Enhancing the above algorithm to keep track of the actual interval groups would actually increase the entire algorithm by a factor of O(n), so we can instead define a separate Find-Solution algorithm to trace back through the array M to find the actual group of intervals that give us the optimal value that we just found:

Find-Solution(j)

• If j=0:
  • output nothing
• Else:
  • If v_j + M[p(j)] >= M[j-1]:
    • Output j together with the result of Find-Solution(p(j))
  • Else:
    • Output the result of Find-Solution(j-1)

This algorithm also runs in O(n) time.

This was a good section, and explained everything quite well. 8/10.

The ideas of dynamic programming became somewhat lost in the recursion in the previous section. Really the important thing is the array M, and once we have that we have solved the problem, because M[n] is the optimal value of the entire problem instance. So, the following algorithm, also O(n) does this:

Iterative-Compute-Opt

• M[0]=0
• For j=1,2,…,n:
  • M[j] = max(v_j + M[p(j)], M[j-1])

To start developing an algorithm based on dynamic programming, we need a collection of subproblems from the original that satisfies the following informal properties:

• only a polynomial number of subproblems
• solution to original problem can be easily computed from the solutions of subproblems (e.g. original prob may actually be one of the subproblems)
• there is a natural order on subproblems like smallest to largest, and an easily computable recurrence that lets us determine the solution to bigger subproblems from the solutions of the smaller ones.

This section was also very well explained and the iterative part couples very nicely with the iterative matrix solving of the knapsack problem that we are doing in class. 9/10.

For this next problem, we introduce another variable to the decision making, rather than a simple binary “yes” or “no” a given interval is in the optimal solution.

Essentially, we have the equation for a best fit line of a given set of points in an x-y plane. However, there are many groupings of points for which using one, two, three, or any number of lines for groupings of contiguous segments of those points that lead to a far better fit. Wanting to minimize the numbers of partitions we divide the full set into, we define a penalty of a partition to be the sum of

• the number of segments into which we partition P (the full set of points) multiplied by a fixed given multiplier C>0
• for each segment, the error value of the optimal line through it.

So, the goal of this Segmented Least Squares Problem is to find a partition of minimal penalty. Note that varying the value of C and such can yield entirely different solutions.

As in the previous section, we can begin with a simple observation: that point p_n belongs to a line segment that begins at some earlier point in the optimal solution. This leads toward an understanding of subproblems–if we know that last segment, then we simply work the same optimality on the remaining points. Denoting the error of a line segment from point i to point n as e_i,j, we have that if the last segment of the optimal partition is from point i to n, then the value of the optimal solution is

• OPT(n) = e_i,j + C + OPT(i-1).

Further, we have the following recurrence for any point j:

• OPT(j) = min_1=<i=<j(e_i,j + C + OPT(j-1)).

So, the algorithm that follows is thus:

Segmented-Least-Squares(n)

• Array M[0…n]
• Set M[0]=0
• For all pairs i=<j:
  • Compute the least squares error e_i,j for the segment from point i to point j
• For j=1,2,…,n
  • Use the recurrence above to compute M[j]
• Return M[n]

The correctness of this algorithm can be proved with induction. We can also trace back through the array M to find the optimal partition:

Find-Segments(j)

• If j=0:
  • output nothing
• Else:
  • Find an i that minimizes e_i,j + C + M[i-1]
  • Output the segment from point i to point j and the result of Find-Segments(i-1)

The total running time of computing all of the e_i,j values for all the pairs is O(n³). After this, though, the total running time is simply O(n²).

Another very good section. They went over everything extremely well and explained the nuance thoroughly. 9/10.