Table 5.1 shows the values within IP-opt for the example shown in figures 5.2 and 5.4. The set of endpoints comprises the values found in the second column of the table; it is assumed that q0=-1. The table is calculated by IP-opt starting at the top with q1 = 3 and proceeding to q10 = 20. The third column contains the value of that leads to the minimum partition costs c(qi) that are shown in the fourth column. An optimal partition for the instance of IP can be derived from the table by the sequence
We note that c(20) corresponds to the minimum number of overlaps for this instance of IP. The optimal partition derived from the table is shown in figure 5.6.
| i | qi | c(qi) | |
|---|---|---|---|
| 1 | 3 | -1 | |
| 2 | 6 | -1 | |
| 3 | 8 | -1 | |
| 4 | 9 | 6 | 2 |
| 5 | 11 | 6 | 2 |
| 6 | 16 | 9 | 5 |
| 7 | 17 | 9 | 5 |
| 8 | 18 | 17 | 9 |
| 9 | 19 | 17 | 9 |
| 10 | 20 | 17 | 9 |