The most dispersed subset of random points in R^d

Consider a population of N individuals, each having (Formula presented) (Formula presented) different traits, and an additive measure, called dispersion, which rewards large pairwise separations between traits. The goal is to select (Formula presented) (Formula presented) individuals such that their traits are as dispersed as possible. We compute analytically the full statistics (including large deviation tails) of the maximally achievable dispersion among sub-populations of size M when the traits are independent and identically distributed. Two complementary approaches are developed, one based on a mean-field theory for order statistics, and the other on the replica method from the field of disordered systems. In all dimensions d, and for rotationally symmetric distributions, the optimal subset for large populations consists of all points lying outside a d-dimensional ball whose radius is determined self-consistently. For a single trait (d = 1), the statistics of the maximal dispersion can be tackled for finite (Formula presented) (Formula presented) as well. The formulae we obtained are corroborated by numerical simulations on small instances and by heuristic algorithms that find near-optimal solutions.