MaxMin selects a maximally dispersed subset of a fixed set of candidate items under the Max-Min Diversity Problem (MMDP, the discrete p-dispersion objective): choose items so that the minimum pairwise distance within the selection is as large as possible.
This dependency-light toolbox operates on three types of input:
- a distance matrix (or
distobject); - Euclidean coordinates, without ever materialising the distance matrix; or
- an on-demand distance-column oracle, for spaces with no coordinate embedding (e.g. phylogenetic trees), where the distance matrix would be too large to store in memory.
Solvers
| Function | Method | Use |
|---|---|---|
Gonzalez() |
Greedy farthest-first (Gonzalez 1985); default best-of-five ensemble of cheap O(N) seeds (centroid, peripheral, 3 reproducible random-furthest starts) | Fast; matrix, coordinate, or distance-column-oracle input (the last for very large sets with no embedding) |
DropAddTS() / DropAddTSPoints()
|
DropAdd tabu search (Porumbel et al. 2011) | ~99%-optimal heuristic |
ExactMaxMin() |
Node-packing integer program (Sayyady & Fathi 2016) | Proven optimum, small n (needs highs) |
PolishSelection() |
Critical-edge 1-swap local search | Refine any selection |
TkScore() |
Minimum pairwise distance (the objective) | Score a selection |
Related packages
The CRAN package maximin constructs continuous space-filling designs — it generates new points in a coordinate box to maximise the minimum inter-point distance.