• Proof:

Correctness

In this section, we show that IP-opt is correct by proving the following

Theorem 28822

The algorithm IP-opt delivers an optimal partition for an instance of IP if there is a partition that satisfies (5.7).  

Proof:

 

(18)

is the invariant of the for-loop in IP-opt where

• that c(q_i) is always forced to be minimal through the min function
• and that P_i is the optimal partition for the segment

If there is no partition that satisfies constraint (5.7) then there must be some q_i such that for all j<i. This causes the set J to be empty and thus the algorithm to report this fact and then to stop. In the remainder of the proof we assume that there is an optimal partition and consequently that J is non-empty for all .

Base case:

i=1
The algorithm provides

with . Thus which causes the sum in (5.11) to evaluate to 0 which matches with (*). Thus the assumption holds.

Hypothesis:

Assume that (5.11) holds for all   (**).

Inductive Step:

i=x+1
Let be the minimising point with j < i = x+1 as guaranteed by the algorithm. Then

Therefore (5.11) holds for i=x+1.