• Definition:

Reducing IP to SGP

Reducing instances of IP to instances of SGP is based on the following observations:

1.

Theorem 1 showed that an optimal partition for an instance of IP can be found within the set E(R) of interval endpoints. Therefore we can certainly find an optimal partition to be found within the set of interval start- and endpoints.

2.

IP wants to minimise the total number of intervals crossing the partition breakpoints p_k ().

3.

Lemma 1 says that the number of intervals in a fragment R_k is the number of intervals that have their startpoint in the partition range (p_k-1,p_k] plus the number of intervals that overlap the left border p_k-1.

Finally, we assign each vertex v the number of intervals that start at the point that corresponds to v as its weight. The sum of vertex weights in a fragment V_k  for SGP is then equivalent to the number of intervals starting at the points that correspond to the vertices in V_k. According to the third observation we need to add the number of intervals that overlap the left border. This number is matched by the lengths of the edge that enters V_k from V_k-1. Figure 5.8 summarises a reduction M  of an instance of IP to an instance of SGP.

Definition:

• X remains unchanged for .
• The graph G=(V,A) is derived in the following way:
  with v_i < v_i+1 for and
       
• Define the the vertex weights:
   
• Define the the edge weights:
  for j=i+1; for convenience we define l(v_i,v_j) = 0 for .