Polynomial-Time Riesz-Energy Subset Selection for Ordered Point Sets on Lines and $\ell_1$-Staircases (opens in new tab)

We study the one-dimensional fixed-cardinality minimum Riesz $s$-energy subset problem with fixed exponent $s > 0$: given ordered real points $x_1 0$, and a cardinality $k$, choose indices $1 \leq i_1 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. Th...