Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution

The Pareto sum of two-dimensional point sets P and Q in ℝ² 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 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 fine-grained equivalent to Bounded Monotone Min-Plus Convolution. Leveraging a remarkable Õ(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. ... mehrOur 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.