Polynomial-Time Riesz-Energy Subset Selection for Ordered Point Sets on Lines and ${\ell }_1$-Staircases

Abstract

We study efficient algorithms for one-dimensional fixed-cardinality minimum Riesz $s$-energy subset selection on ordered real-line point sets and propose and test a polynomial-time exact s-t cut-based algorithm for this problem. Given $x_1<\cdots <x_n$, an exponent $s>0$, and a cardinality $k$, the task is to choose $1\le i_1<\cdots <i_k\le n$ minimizing $E_s(i_1,\dots ,i_k)={\sum }_{1\le p<q\le k}(x_{i_q}-x_{i_p}{)}^{-s}$. We prove that the one-dimensional Riesz interaction satisfies a Monge inequality. When feasible subsets are encoded as increasing index vectors, this property implies submodularity on a finite distributive lattice and yields polynomial-time solvability by submodular minimization over such lattices. The structural reduction holds for every real $s>0$. We also derive an explicit minimum $S$--$T$ cut formulation with $k(n-k)$ threshold variables and $O(k^2(n-k{)}^2)$ finite pairwise edges. The constructed 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)$ cut step, while the conservative $O(N^{2}M)$ bound gives $O(k^4(n-k{)}^4)$. By an isometry argument, the same algorithm applies to ${\ell }_1$-staircases, including monotone two-dimensional Pareto-front and skyline approximations. The accompanying Python implementation includes verification examples and an empirical runtime benchmark; on balanced instances $n=2k$, the reference min-cut code overtakes exhaustive enumeration around $n=24$--$26$. The appendix provides examples and detailed explanations of the underlying theory.

18pages, 6 Figures; corrected the examples for min-cut; formatting improvement; additional sentence at the end of appendix