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: njobs,  ith 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 Si 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: