# Integrating Pareto Optimization into Dynamic Programming
## 4 Experiments
### Comparing Two Sorting Strategies  
In Experiment 4, we test the sorted variant of strategy EAGER on the same four ADP applications as before and compare it to the simplest version of SORT, _i.e._, SORT(1), which uses the off-the-shelf Quicksort algorithm. Our goal is to find possible separators, where one method becomes better than the other, suggesting a data-dependent switch between methods (as we did in Experiment 1). Again, the tests were executed in 2 steps, first comparing the runtimes at the level of intermediate subproblems, excluding the runtime of the surrounding code, and afterwards comparing the full running times of the best implementations. As separators, linear and exponential separations based on values of \(N\) and \(M\) are considered, motivated by the asymptotic complexity of the compared implementations that differ in the factors of these two variables. A summary of the results is shown in Table 5.  
Figure 4: Runtime gain of individual data points of Algorithm 7 against Algorithm 1 for the test cases (**a**) Fold2D and (**b**) Gotoh2D. Points are plotted when one algorithm performed better than the other with point sizes relative to the gained time. Gotoh2D shows only very little variance in list sizes contrary to Fold2D, explaining the performance differences. There are two main observations. First of all, no separators are given for any case. The reason for this is that in no case could any improving separators be found. In all cases, one algorithm performs best for all data points. Secondly, with the exception of Gotoh2D, for two-dimensional definitions, EAGER(sorted) always performed best, whereas for higher dimensions, SORT(1) is superior without failure. The explanations for both facts are not entirely unrelated. The difference between dimensions is of course a result of the different underlying implementations of Merge 1 and Merge 2. As before, we see that more than half of the full running times are spent in Pareto operators. The two-dimensional case is very similar to the sorted case, only that we apply Pareto operators, as well as sorting the elements. In a way, Merge 1 works similar to a normal two-way merge sort with a merge step definition that is not in place, reflected by the complexity of \(O(N\log(M))\). By the same arguments as before, Merge 1 is likely to perform better than executing a sorting in \(O(N\log(N))\) when \(M<<N\). Conversely, if the number of sublists \(M\) is near the number of elements \(N\) and sublists are very short, the sorted case with Algorithm 1 will perform better. As intermediate lists are created by combining sub-results, the lengths of individual sub-results are likely to stay over a certain threshold that seems to be high enough in order for Merge 1 to perform well. For higher dimensions, the situation changes, as now both algorithms perform in \(O(N^{2})\), the complexity of the Pareto operations now dominating the sorting aspects of both implementations. However, the additional factors brought in by the different scenarios strongly favor the use of Algorithm 1 and a single operator step, compared to multiple smaller operator steps, each in \(O(N^{2})\). This seems to be true already for small \(N\) and, accordingly, only grows worse for longer candidate lists. The scatter plots in Figure 4(a),b confirm this theory for both cases. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Name** & **Input Size** & **Front Size** & **Gain (s)** & **Separator** & **Sort (s)** & **SORT(1) (s)** & **EAGER(sort) (s)** \\ \hline Ali2D & 509 & 487 & 220.46 & - & 220.1 & 579.77 & **356.11** \\ Gotoh2D & 249 & 209,744 & - & - & 0.1 & 29.42 & 29.83 \\ Fold2D & 608 & 13 & 762.16 & - & 542.3 & 2220.24 & **1054.39** \\ Prob2D & 185 & 9 & 0 & - & 1.7 & 3.64 & **2.76** \\ Ali3D & 200 & 446 & - & - & 4.3 & **4.97** & 8.04 \\ Fold3D & 404 & 165 & - & - & 5757.9 & **841.64** & 5810.36 \\ Prob4D & 185 & 2327 & - & - & 14,442.3 & **2556.83** & 14,552.12 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Summary of computation times and metadata of test cases.