The most dispersed subset of random points in R d
Open Access
- 13 April 2026
- journal article
- Published by IOP Publishing in Journal of Physics A: Mathematical and Theoretical
- Vol. 59 (17)
Abstract
Consider a population of N individuals, each having d ≥ 1 different traits, and an additive measure, called dispersion, which rewards large pairwise separations between traits. The goal is to select M ≤ 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 nearoptimal solutions.Keywords
All Related Versions
Funding Information
- UKRI FLF Scheme (MR/X023028/1)
- Universita degli Studi di Bari Aldo Moro (2023-UNBACLE-0245516)
- Istituto Nazionale di Fisica Nucleare INFN (2022TEB52W-PE1-)
- Istituto Nazionale di Fisica Nucleare INFN (CN00000013)
- Gruppo Nazionale di Fisica Matematica GNFM-INdAM
- PNRR MUR (PE0000023-NQSTI)
This publication has 30 references indexed in Scilit:
- The quadratic knapsack problemEuropean Journal of Operational Research, 2024
- A fast and effective breakpoints heuristic algorithm for the quadratic knapsack problemEuropean Journal of Operational Research, 2024
- Spin glass theory and its new challenge: structured disorderIndian Journal of Physics, 2023
- A review on discrete diversity and dispersion maximization from an OR perspectiveEuropean Journal of Operational Research, 2022
- Asymptotic behavior of the quadratic knapsack problemEuropean Journal of Operational Research, 2016
- Topology Trivialization and Large Deviations for the Minimum in the Simplest Random OptimizationJournal of Statistical Physics, 2013
- Heuristics and metaheuristics for the maximum diversity problemJournal of Heuristics, 2011
- Computational aspects of the maximum diversity problemOperations Research Letters, 1996
- Analytical models for locating undesirable facilitiesEuropean Journal of Operational Research, 1989
- Quadratic knapsack problems1980