Correctness

Next: Optimal Solution for SGP Up: Alternative: Reducing IP to Previous: Example

Subsections

Correctness

We now prove formally that the reduction that has been presented in the previous section delivers an optimal solution for IP.

Theorem 28963

Using the reduction M described in figure 5.8, each partition P for an instance

of SGP that satisfies the constraints of SGP satisfies also the constraints of the IP problem for the instance of IP.

Proof:

The optimal partition P of being also an optimal partition for means that

(21)

for . We show that the constraints imposed by IP and SGP are equivalent, i.e. that (5.12) and (5.13) holds for exactly when (5.6) and (5.7) holds for . For this purpose we prove the following relationships:

5.15)

Proof of (

As a first step we look at how translates into an expression based on the lengths of edges in the graph. Let be the closest start- or endpoint bigger than p. We construct:

This means that

We now have to prove that for each there is a and vice versa, i.e.

But (**) follows from

From (*) and (**) follows that (5.15) holds.

5.16)

Proof of (

This proof is based on the third observation made earlier, i.e. lemma 1 with (5.8). It said that the number of intervals in a fragment R_k is (a) the number of intervals having the startpoint in (p_k-1,p_k] plus (b) the number of intervals that overlap the left border p_k-1. By the definition of w(v) it is obvious that (a) corresponds to

We now look at the equivalence of (b) to the second sum in (5.13). To this end, we can show that each A_k consists only of one element; remember the definition of a p_k in (5.14):

which means that

(5.16) therefore follows from (*) and (**).

Next: Optimal Solution for SGP Up: Alternative: Reducing IP to Previous: Example

Thomas Zurek