Statistics of Partial Minima
E. Ben-Naim, M. B. Hastings, D. Izraelevitz
Motivated by multi-objective optimization, we study extrema of a set
of N points independently distributed inside the d-dimensional
hypercube. A point in this set is k-dominated by another point when at
least k of its coordinates are larger, and is a k-minimum if it is not
k-dominated by any other point. We obtain statistical properties of
these partial minima using exact probabilistic methods and heuristic
scaling techniques. The average number of partial minima, A, decays
algebraically with the total number of points, A ~ N^{-(d-k)/k}, when
1<=k
source,
ps,
pdf