Posted by: atri | December 4, 2009

## Lect 36: Weighted Interval Scheduling

(Guest post by Santosh Thapa)

Prof Atri started lecture with some recap about weighted interval schedule. Here, he discussed that all jobs are sorted by their finish time and all inputs for weighted interval schedule have non-negative value and output will be a set of schedules which is optimal and our goal is to have maximum optimal solution.

• Input: $n$jobs,  $i$th job  $(s_i,f_i,v_i)$ which stand for start time, finish time, and value respectively, sorted according to finishing time.
• Output: A schedule  $S\subseteq \{1,\dots,n\}$ where for  $i\neq j\in S$$i$ and  $aj$ re not conflicting.
• Goal: max  $\sum_{i\in S} v_i$

Recall we proved last time that

$OPT(j) = max \{ v_j + OPT (p(j)), OPT (j-1)\}$

We could have two option for $j$, it could be in $\mathcal{O}_j$ and it could not be in $\mathcal{O}_j$. And it can be done in linear time.

Question: How can we figure out if $j$ in optimal solution or not (given the values $OPT(1),\dots,OPT(j-1)$)?
Answer: Once we know the value of all optimal solutions, we could compare $v_j+OPT(p(j))$ to $OPT(j-1)$  and if the first term is greater then $j$ is in a optimal schedule.

Professor mentioned that Dynamic programming is similar to Divide and Conquer, where both use recursion but Dynamic programming uses different kind of recursion. In other words, dynamic programming is smarter about solving recursive sub problems.

To compute $OPT(j)$, he discussed about its algorithm using property of optimality, which is

$Compute-OPT( j)$

1. If $j = 0$, return $0$
2. return $\max \{ v_j + Compute-Opt( p(j) ), Compute-Opt( j-1 ) \}$

To prove this algorithm he started proving Lemma.

Lemma: For every $0 \le j \le n$, $OPT(j) = Compute-OPT(j)$.

Proof Idea: Induction on $j$

Base Case: if $j =0$, $Compute- OPT(0) = 0 = OPT(0)$.
Inductive Hypothesis: For $i < j$, $OPT(i) = Compute-OPT(i)$

Inductive Step: Since, $j > 0$ return value is $\max\{ v_j + Compute-OPT(P(j)), Compute-OPT(i)\}$. By the IH, $Compute-OPT(p(j))=OPT(p(j))$ and $Compute-Opt(j-1)=OPT(j-1)$, the proof follows from the recursive formula for $OPT(j)$.

Running time: Exponential

Example:

Here for each job value, it need to call recursively. So, it is exponentially recursive.  But important aspect of this kind of algorithm will be helpful in while doing re-computation, which can be done very quickly by storing the recursive value. Even, though it takes more memory, but it will help in solving problem faster.

At the end of the lecture, he wrote the algorithm. We will need a global array $M[j] = null$ or $OPT(j)$.

$MCompOPT(j)$

1. If $j = 0$, return $0$
2. If $M[j] \neq null$, return $M[j]$
3. $M[j] = max\{v_j + MCompOpt(p(j)), MCompOPT(j-1)\}$
4. Return $M[j]$

End of the lecture. Continue of Dec 4th.

Advertisements