Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution
This work addresses a bottleneck in bi-criteria optimization algorithms by offering efficient approximations for Pareto sums, which is incremental as it builds on prior exact algorithms and theoretical connections.
The paper tackles the problem of efficiently approximating Pareto sums in bi-criteria optimization, which has conditional lower bounds preventing strongly subquadratic exact algorithms, and achieves a conditionally optimal approximation algorithm with a runtime of $ ilde{O}(n^{1.5})$ by connecting it to Bounded Monotone Min-Plus Convolution, while also providing practical implementations that trade off approximation quality and running time.
The Pareto sum of two-dimensional point sets $P$ and $Q$ in $\mathbb{R}^2$ is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the Pareto sum arises frequently in bi-criteria optimization algorithms. Prior work establishes that computing the Pareto sum of sets $P$ and $Q$ of size $n$ suffers from conditional lower bounds that rule out strongly subquadratic $O(n^{2-ε})$-time algorithms, even when the output size is $Î(n)$. Naturally, we ask: How efficiently can we \emph{approximate} Pareto sums, both in theory and practice? Can we beat the near-quadratic-time state of the art for exact algorithms? On the theoretical side, we formulate a notion of additively approximate Pareto sets and show that computing an approximate Pareto set is \emph{fine-grained equivalent} to Bounded Monotone Min-Plus Convolution. Leveraging a remarkable $\tilde{O}(n^{1.5})$-time algorithm for the latter problem (Chi, Duan, Xie, Zhang; STOC '22), we thus obtain a strongly subquadratic (and conditionally optimal) approximation algorithm for computing Pareto sums. On the practical side, we engineer different algorithmic approaches for approximating Pareto sets on realistic instances. Our implementations enable a granular trade-off between approximation quality and running time/output size compared to the state of the art for exact algorithms established in (Funke, Hespe, Sanders, Storandt, Truschel; Algorithmica '25). Perhaps surprisingly, the (theoretical) connection to Bounded Monotone Min-Plus Convolution remains beneficial even for our implementations: in particular, we implement a simplified, yet still subquadratic version of an algorithm due to Chi, Duan, Xie and Zhang, which on some sufficiently large instances outperforms the competing quadratic-time approaches.