{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicytc4hnyr4yikl6ny6elhmzq2yee7t4n6mp6r3tsxamywh2txkdm",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkosgw7zfd62"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.26929v1",
  "publishedAt": "2026-04-30T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Michael T. M. Emmerich"
  ],
  "textContent": "**Authors:** Michael T. M. Emmerich\n\nWe 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",
  "title": "Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases"
}