The Most Dispersed Subset of Random Points in ${\mathbb{R}}^d$

Abstract

Consider a population of $N$ individuals, each having $d\ge 1$ different traits, and an additive measure, called dispersion, which rewards large pairwise separations between traits. The goal is to select $M\le N$ 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 $N,M$ as well. The formulae we obtained are corroborated by numerical simulations on small instances and by heuristic algorithms that find near-optimal solutions.

35 pages, 7 figures, typos fixed. Published version

References in corpus (7)

• The large deviation approach to statistical mechanics
• Topology trivialization and large deviations for the minimum in the simplest random optimization
• Quadratic stochastic Euclidean bipartite matching problem
• Spin glass theory and its new challenge: structured disorder
• Maximal Diversity and Zipf's Law
• Random Euclidean matching problems in one dimension
• A Fast and Effective Breakpoints Heuristic Algorithm for the Quadratic Knapsack Problem

Cited by in corpus (1)

• Maximal Minimal Spacing for Random Points