{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibvslxc2nto2ttr2hfhumq4d7zpuviahaj5f5vmq7ustjvytpd7gu",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mof4guxynhp2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.16946v1",
  "publishedAt": "2026-06-16T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Michael T. M. Emmerich"
  ],
  "textContent": "**Authors:** Michael T. M. Emmerich\n\nWe study the one-dimensional fixed-cardinality minimum Riesz $s$-energy subset problem with fixed exponent $s > 0$: given ordered real points $x_1 < x_2 < \\cdots < x_n$, a positive parameter $s>0$, and a cardinality $k$, choose indices $1 \\leq i_1 < \\cdots < i_k \\leq n$ minimizing $E_s(i_1,\\ldots,i_k)=\\sum_{1\\leq p\"0$; bit-complexity claims require the arithmetic assumptions stated in the complexity section. The same structure also yields an explicit minimum $S$--$T$ cut algorithm with $k(n-k)$ threshold variables and $O(k^2(n-k)^2)$ finite pairwise edges. The resulting graph has $N=k(n-k)$ nodes and $M=O(k^2(n-k)^2)$ arcs after an $O(k^2(n-k)^2)$ coefficient-construction step; an $O(NM)$ max-flow bound gives an $O(k^3(n-k)^3)$ min-cut step, while the conservative $O(N^2M)$ bound gives $O(k^4(n-k)^4)$. Due to isometry, the results apply directly to subset selection on $\\ell_1$ staircases, such as choosing diverse and representative Pareto front or skyline approximations in two dimensions. An open-source Python implementation of the min-cut algorithm accompanies the reproducibility material.\"",
  "title": "Polynomial-Time Riesz-Energy Subset Selection for Ordered Point Sets on Lines and $\\ell_1$-Staircases"
}