Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases

This paper studies exact fixed-cardinality Solow–Polasky diversity subset selection on ordered finite ${\mathrm{\ell }}_1$ point 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^{-qd(x_i,x_j)}$, the quantity ${\text{1}}^{\mathrm{\top }}{Z}^{-1}\text{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, the paper gives a detailed proof of the scaled consecutive-gap identity $\text{SP}(X)=1+{\sum }_r\tanh (q{g}_r\mathrm{/}2),$ where the $g_r$ are the gaps between consecutive selected points. It then proves an exact Bellman-recursion theorem for maximizing this value over all subsets of a prescribed cardinality, yielding an $O(k{n}^2)$ dynamic program for an ordered $n$-point candidate set and subset size $k$. Finally, the paper proves ordered ${\mathrm{\ell }}_1$ reductions showing that the same algorithm applies to monotone biobjective Pareto-front approximations and, more generally, to finite coordinatewise monotone ${\mathrm{\ell }}_1$ staircases in ${\mathbb{R}}^d$. These are precisely the ordered ${\mathrm{\ell }}_1$ chains for which the ${\mathrm{\ell }}_1$-distance becomes a line metric along the chosen order, so the one-dimensional dynamic program applies without modification. Keywords: Solow–Polasky diversity; magnitude; metric geometry; dynamic programming; ordered points; ${\mathrm{\ell }}_1$ geometry; Pareto-front approximation.