Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
2026-04-29 • Computational Geometry
Computational GeometryData Structures and Algorithms
AI summaryⓘ
The authors study how to select a fixed-size subset from an ordered set to maximize a measure called Solow--Polasky diversity, which is mathematically connected to a concept known as magnitude in metric geometry. They focus on sets ordered in one dimension and their extensions to higher-dimensional monotone staircases, where distances behave like sums of gaps. Using previous formulas, the authors prove an identity relating diversity to the gaps between points, then develop a dynamic programming method to find the best subset efficiently. They also show that this approach applies to approximating Pareto fronts in biobjective and multiobjective optimization problems with certain ordered structures.
Solow-Polasky diversitymagnitudemetric geometrydynamic programmingPareto frontmultiobjective optimizationordered setsℓ₁ metricBellman recursionline metric
Authors
Michael T. M. Emmerich
Abstract
We study exact fixed-cardinality Solow--Polasky diversity subset selection on ordered finite $\ell_1$ sets, with monotone biobjective Pareto fronts and their higher-dimensional staircase analogues as central applications. Solow--Polasky diversity was introduced in biodiversity conservation, whereas the same inverse-matrix expression appears in metric geometry as magnitude: for a finite metric space $(X,d)$ with exponential similarity matrix $Z_{ij}=e^{-q d(x_i,x_j)}$, the quantity $\1^\top Z^{-1}\1$ is the magnitude of the scaled finite metric space $(X,qd)$ whenever the weighting is defined by the inverse matrix. Thus, in this finite exponential-kernel setting, Solow--Polasky diversity and magnitude are mathematically the same object viewed through different motivations. Building on the linear-chain magnitude formula of Leinster and Willerton, we provide a detailed proof of the scaled consecutive-gap identity $ \SP(X)=1+\sum_r \tanh(qg_r/2), $ where the $g_r$ are the gaps between consecutive selected points. We then prove an exact Bellman-recursion theorem for maximizing this value over all subsets of a prescribed cardinality, yielding an $O(kn^2)$ dynamic program for an ordered $n$-point candidate set and subset size $k$. Finally, we prove ordered $\ell_1$ reductions showing that the same algorithm applies to monotone biobjective Pareto-front approximations and, more generally, to finite coordinatewise monotone $\ell_1$ staircases in $\R^d$. These are precisely the ordered $\ell_1$ chains for which the Manhattan metric becomes a line metric along the chosen order, so the one-dimensional dynamic program applies without modification. Keywords: Dynamic Programming, Solow--Polasky Diversity, Complexity Theory, Multiobjective Optimization, Pareto front, Magnitude