Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm reading a dynamic programming algorithm to the weighted interval scheduling problem. There are $n$ intervals, each has a start time $s_i$, a finishing time $f_i$ and a value $v_i$. The goal is to find a subset of intervals with the maximum total of values. Let $p(j)=i$ be the left-most interval $i$ that finishes before interval $j$ begins.

Can you explain this reasoning:

"If interval $n$ (the last one) belongs to an optimal solution $O$, then $O$ must include an optimal solution to the problem consisting of intervals $\{1,...,p(n)\}$ -- for if it didn't, we could replace $O$'s choice of intervals from $\{1,...,p(n)\}$ with a better one, with no danger of overlapping n."

In particular, I don't understand how I can "replace the optimal solution with a better one". Thank you.

Below is the scanned copy of what I'm reading. My question is about the last sentence.

scanned copy of the reading

share|improve this question
    
Not sure if my answer is exactly what you're looking for, but let me know if you could use any more help. –  user17794 Jun 19 '12 at 17:48
add comment

1 Answer

up vote 0 down vote accepted

When a dynamic programming approach applies to a problem of interest, showing the optimal subproblem property typically boils down to the following approach:

a) Name an optimal solution to the original problem

b) Consider a generic subproblem and name its solution

c) Suppose the solution from part b) does not sit inside of the solution from part a) and derive a contradiction

There is a slight abuse of notation in the last paragraph; the set $\{ 1, ..., p(n) \}$ does not consist of requests, but rather request indices. Now, since $p(n)$ is the maximal index $j$ such that intervals $j$ and $n$ are disjoint, the case $n\in \mathcal{O}$ leads us to consider the subproblem of interval scheduling for requests $\{ f_1, ... , f_{p(n)} \}.$

Let $\{ i_1, i_2 , ..., i_n, n \}$ be an optimal interval schedule for the original problem and $\{ j_1, ... , j_m, \}$ be an optimal interval schedule for the aforementioned subproblem. This means that $\displaystyle\sum_{k=1}^n v_{i_k} \le \displaystyle\sum_{k=1}^m v_{j_k}.$ Suppose that there exists $k$ ($1\le k \le m$) such that $j_k \notin \mathcal{O}.$ Since $j_m \le p(n)$ (this is immediate by our statement of the subproblem), we can consider the interval schedule $\{ j_1, ... , j_m, n \}$ for our original problem. Using the previous inequality, we see that $(\displaystyle\sum_{k=1}^n v_{i_k} ) +n \le (\displaystyle\sum_{k=1}^m v_{j_k}) +n,$ contradicting the optimality of $\{ i_1, i_2 , ..., i_n, n \}.$

share|improve this answer
    
what do you mean by "name a(n) (optimal) solution"? –  cody Jun 22 '12 at 20:18
    
For instance, in the solution I provided, the name of the optimal solution is $\{ i_1, i_2 , ..., i_n , n \}.$ –  user17794 Jun 23 '12 at 1:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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