• Algorithm IP-opt

Algorithm for Optimal Partitioning

A dynamic programming approach can be used for computing an optimal solution for IP if there is such. An optimal partition can be found amongst the set of endpoints as we have seen from theorem 1 in the previous section. We will refer to the elements in the set of endpoints as with q_i < q_i+1 for all .

We first describe the algorithm IP-opt informally. It starts with q₁ and goes through to q_n. For each q_i it will hold the necessary information for an optimal partition for the span ending at q_i, i.e. for the segment , with all intervals in R intersecting with the partial span being considered. The algorithm computes two items of information for each q_i:

• c(q_i) = the cumulative total number of overlaps for the selected optimal partition up to q_i,  
•   if q_j is the previous breakpoint that led to this minimum.  

There is no optimal partition if - for any q_i - there is no q_j with j<i such that the number of intervals intersecting with the segment (q_j,q_i], i.e. , is less than the maximum load of X intervals. The loads involving the dummy point are defined as

The algorithm then looks as shown in figure 5.5.

Algorithm IP-opt

• c(q₀) = 0
• for i=1 to n do
  • if then
    output ``No optimal partition.'' ; stop.
  • 
    Let for the minimising q_j.
    If there is more than one qualifying q_j then choose the smallest.
• [] /* output of breakpoints in descending order */
• p=q_n
• while do
  • output p

The algorithm IP-opt for computing an optimal partition for an instance of IP.

The run time complexity is O(n²) as the min-function is O(n). Computing the values for the -function is O(n²) and can be done beforehand. Similarly, computing the values for is O(n).