4
$\begingroup$

Say that there are $n$ days and there is $x_1, x_2, ...,x_n$ amount of data to process on each day. Your computer can process $s_1$ amount of work on the first day since rebooting your computer, $s_2$ work on the second day since a reboot, up to $s_n$. On each consecutive the day the amount of work your computer can perform without being rebooted decreases. In other words, $s_1 >s_2>...>s_n>0$. Any day you reboot your system you cannot do any work.

The problem is to find an algorithm using dynamic programming to figure out the maximum amount of work possible given $x_1...x_n$ and $s_1...s_n$. This means we must determine which day(s), if any, we should reboot on.

For example:

n| 1 | 2 | 3 | 4
x| 8 | 3 | 11| 5
s| 9 | 4 | 2 | 1

The most optimal solution here would be to reboot on day 2, so that we can perform 8 work on day 1, 9 work on day 3, and 4 work on day 4 for a total of 21.

This seems somewhat similar to the partition problem but I am having trouble coming up with a recurrence relation I can convert to dynamic programming.

If we say that our final reboot occurs on day $i$, then our maximum work should be the amount of work done from days $i$ to $n$ plus the maximum work we can do on days $1$ to $i-1$.

So if we say $M[x_1...x_m,s_1...s_n]$ represents the maximum amount of work we can do on days $1$ to $m$, I write the following recurrence relationship:

$$M[x_1...x_m,s_1...s_n] = \max_{i=1}^m\{M[x_1...x_{i-1},s_1...s_n]+R[i]\}$$

Where $R[i]$ is simply the max amount of work you can do from days $i$ to $n$ without rebooting, which is simple to calculate.

Does this seem like it is a valid recurrence relation? Also, I am not quite sure what my base cases would be. Perhaps that $M[x,s] = \{x$ if $s \geq x$ else $s\}$? I am not sure if this covers all possibilities though.

$\endgroup$
  • $\begingroup$ $R[i]$ should be from $i$ to $m$, I think because to drive $M[m]$ you need the calculate the subproblems first. Other than this it looks more or less correct. $\endgroup$ – jjohn Nov 1 '15 at 23:30
5
$\begingroup$

This seems to be exercise 9 from Kleinberg's Algorithm Design, chapter six. I'll report how i tried to solve it.

Let's define $OPT(i)$ as the maximum amount of work from day $1$ to day $i$, with $i \leq n$

For every $i$, there can be a reboot in any previous day $1\leq j < i$. If it was on day $j$, than you processed $\sum_{k=j+1}^i \min\left\{s_{k-j}, x_k\right\}$ terabytes. Furthermore, on day $j$ you cannot process anything. Than you can define the following recurrence relation: $$ OPT(i) = \displaystyle\max_{1\leq j < i} \left\{\displaystyle\sum_{k=j+1}^i \min\left\{s_{k-j}, x_k\right\} + OPT(j-1)\right\} $$

The algorithm can be implemented in a bottom-up fashion, with $O(n^3)$ running time:

let OPT[0...n] be a new array of n+1 elements
OPT[0] = 0, OPT[1] = min(s[1], x[1])
for i = 2 to n
  m = -infinity
  for j = 1 to i-1
    l = 0
    for k = j+1 to i do l = l + min(s[k-j], x[k])
    l = l + OPT[j-1]
    if l > m then m = l
  OPT[i] = m
return OPT[n]   

There is also a $O(n^2)$ solution based on a matrix of subproblems. Define $OPT(i, j)$ as the maximum from day $i$ to $n$ with last reboot done $j$ days before, more exactly on $i-j$ day. For every day $i$ you have to consider these alternatives:

  • you have a reboot. So on day $i$ you cannot process anything: $OPT(i,j) = OPT(i+1, 1)$
  • go on with processing: $OPT(i,j) = \min\left\{s_j, x_i\right\} + OPT(i+1, j+1)$

Because it's of no use reboot on last day, you have $OPT(n,j) = \min\left\{s_j, x_n\right\}$.

This last approach is taken from Mangat Rai's work, a user that shared a collection of solutions to Kleinberg's book problems, although the first one i reported is also very close to what you can find there. I suggest you to do a web search for it (no official site as far as i know).

$\endgroup$
  • $\begingroup$ Thanks a lot, your solution is very helpful. I am wondering what you mean by a bottom-up fashionn for the $O(n^3)$ algorithm. Also, what would be the base case for this recurrence? Perhaps that $OPT(1) = \min\{s_1,x_1\}$? $\endgroup$ – flubsy Nov 2 '15 at 23:46
  • 1
    $\begingroup$ Yes, i think it is correct but you need also to put $OPT(0)=0$ because $j$ can be equal to $1$ and a value for $OPT(j-1)$ is always required. Basically you start from the smallest value of $i$ applying iteratively the recurrence relation to set properly values in the $OPT$ array. At the end, $OPT(n)$ contains the solution. Edited the post to include pseudo implementation. $\endgroup$ – kentilla Nov 3 '15 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.