# Integrating Pareto Optimization into Dynamic Programming
## 2 Key Operations in Pareto Optimization and Dynamic Programming  
In this section, we collect the technical definitions of certain key operations, which we will combine in various ways in our experiments. Domination is the key concept in Pareto optimization. For simplicity, we start the discussion with two dimensions and comment on multi-dimensional Pareto optimization below (Pareto optimization implies that there are at least two dimensions; we reserve the term \"multi-dimensional\" for the case of three or more dimensions). Consider two sets \(A\) and \(B\), which are totally ordered by relations \(>_{A}\) and \(>_{B}\), respectively. We say \((a,b)\in A\times B\) dominates \((a^{\prime},b^{\prime})\in A\times B\) if \(a\geq_{A}a^{\prime}\) and \(b>_{B}b^{\prime}\), or if \(a>_{A}a^{\prime}\) and \(b\geq_{B}b^{\prime}\). Note that domination is a partial ordering (Think of shipping goods, with offers measured in terms of travel time and cost. Both are to be minimized, so the order underlying domination is actually \(<\). Offers, such as (seven days, 100%) and (two days, 180%), are incomparable in the domination ordering and, therefore, constitute an interesting trade-off. An offer such as (two days, 220%) is dominated by (two days, 180%) and, hence, irrelevant. The Pareto front of a set \(X\subseteq A\times B\) is the subset of elements that are not dominated by others, more formally:  
\[\mathbf{pf}_{>_{A},>_{B}}(X)=\{(a,b)\in X|\ \ \
ot\exists(a^{\prime},b^{ \prime})\in X\setminus\{a,b\}\text{ with }a\leq_{A}a^{\prime},b\leq_{B}b^{\prime}\}. \tag{1}\]  
We will drop the subscripts from \(\mathbf{pf}\) where clear from the context. The practical appeal of these definitions is that domains \(A\) and \(B\) are unrelated, each with its specific ordering. Values can be days, dollars, probabilities, energies or any kind of score. If you ever have to balance love over gold, Pareto optimization is your method of choice. The Pareto front size for a random set \(X\) of size \(N\) is expected as \(H(N)\), where \(H\) is the harmonic number and closely related to \(\log(N)\)[22; 23]. This interacts in a fortunate way with dynamic programming, where for input size \(n\), the search space \(X\) grows with \(O(2^{n})\), and we can expect Pareto fronts of size \(O(n)\). This has been confirmed in practice in [21]. Pareto front computation can be achieved in \(O(N)\) when \(X\) is lexicographically sorted. When unsorted, we can first sort \(X\) in \(O(N\log(N))\) and then compute the Pareto front in linear time, achieving worst case \(O(N\log(N))\). However, relying on the harmonic law, we can expect \(\mathcal{O}(N\log(N))\) runtime also from a direct computation of the \(O(N^{2})\) worst case, because one factor \(N\) stems from the size of the constructed Pareto front, and due to the harmonic law, it reduces to \(\log(N)\)[21]. Algorithmic building blocks for our experiment will be both sorted and unsorted implementations of \(\mathbf{pf}\). From the experimental point of view, different \(O(N\log(N))\) sorting algorithms must be considered. Multi-dimensional Pareto optimization can be defined analogously to the above definition. For \(d>2\) dimensions, the Pareto front size for a random set \(X\) of size \(N\) is expected as \(H^{(d)}(N)\), where \(H^{(d)}\) is the generalized harmonic number and closely related to \(\log^{d-1}(N)\)[23]. Hence, increasing the dimension increases the expected front size exponentially. As runtime complexity, we lose \(O(N)\), even on sorted \(X\), but a sophisticated algorithm exists (we call it \(\mathbf{pf}_{bentley}\)) that computes \(\mathbf{pf}(X)\) in worst case \(O(N\log^{d-1}(N))\)[23; 24]. We have also implemented the multi-dimensional Pareto product in [PERSON]'s GAP. In practice, however, Pareto front sizes quickly become unmanageable for many applications, although three-dimensional optimization is still common. Key operations in (algebraic) dynamic programming must be identified that call on Pareto operations.