Showing cs.CGShow all
3 papers · 1 filter
cs.CG2026
On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
Michael T. M. Emmerich, Ksenia Pereverdieva, André Deutz
We study the computational complexity of exact cardinality-constrained minimum Riesz -energy subset selection in finite metric spaces: given points, select points of m…
cs.CG2026
Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
Michael T. M. Emmerich, Ksenia Pereverdieva, André H. Deutz
We prove that, for every fixed , selecting a subset of prescribed cardinality that maximizes the Solow--Polasky diversity indicator is NP-hard for finite point sets in $\ma…
cs.CG2026
Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
Michael T. M. Emmerich, Ksenia Pereverdieva, André H. Deutz
The Solow--Polasky diversity indicator (or magnitude) is a classical measure of diversity based on pairwise distances. It has applications in ecology, conservation planning, and, m…