Exact and Fast Subset Selection Algorithms for the Bi-objective Integral R2 Indicator
2026-06-22 • Computational Geometry
Computational GeometryData Structures and Algorithms
AI summaryⓘ
The authors study how to pick the best fixed-size group of points from a set that approximate a two-objective problem using a special continuous measure called the integral bi-objective R2 indicator. They develop an exact dynamic programming method that breaks the problem down into simpler parts and initially runs in O(kn²) time. By proving the problem has a special property called the Monge condition, they improve the method to faster versions running in O(kn log n) and even O(kn) time. Their approach is exact for continuous settings and differs from simpler methods that use only a finite number of weights. They also provide Python code to compare all their methods and verify correctness.
fixed-cardinality subset selectionbi-objective optimizationR2 indicatorTchebycheff scalarizing functionPareto frontdynamic programmingMonge matrixdivide and conquerexact algorithmintegral indicator
Authors
Michael T. M. Emmerich
Abstract
We study fixed-cardinality subset selection for the exact integral bi-objective $R_2$ indicator with a uniform continuum of weighted Tchebycheff scalarizing functions. The indicator measures the area under the lower envelope of scalarizing losses over weight space, rather than a finite sample average over weight vectors. For a sorted bi-objective Pareto-front approximation, represented by points ordered by increasing first objective and decreasing second objective, we derive an exact adjacent-neighbor decomposition of this integral objective into boundary terms, unary diagonal corrections, and selected-neighbor transition terms. This yields an exact Bellman dynamic program with $O(kn^2)$ running time for selecting $k$ of $n$ candidate points. We then prove that the transition matrix is Monge. This gives a divide-and-conquer implementation with $O(kn\log n)$ running time and, more strongly, a staircase matrix-search implementation with $O(kn)$ running time under constant-time arithmetic comparisons. The matrix-search proof is presented through a lower-envelope sweep over single-crossing transition functions and includes the triangular feasibility condition $i<j$. The algorithms are exact for the continuous integral $R_2$ setting and are distinct from finite-weight-vector approximations, although they are related to earlier exact and dynamic-programming work on two-dimensional indicator-based subset selection, including hypervolume subset selection. Reproducible Python code compares exhaustive enumeration, the direct left-to-right dynamic program, the divide-and-conquer dynamic program, and the matrix-search implementation under explicit consistency checks.