Skip to content

RDKit MaxMinPicker

RDKit is a cheminformatics toolkit, and its MaxMinPicker is farthest-point traversal: start somewhere, then repeatedly take whichever remaining item is furthest from everything picked so far.

Its distinguishing feature here is not the algorithm — several tools implement the same traversal — but the interface. It takes a distance function, not a matrix, and evaluates it lazily. That single decision is why it is the only tool in this comparison that stays practical into the millions: nothing ever needs all \(n^2\) distances to exist simultaneously.

The trade is that it does one thing. One objective, no constraints, no budget to spend, and no way to improve the answer by waiting.

Problem targeted

Given \(n\) items, a distance \(d(i,j)\) and a target size \(k\), it greedily constructs \(S\) by

\[ S \leftarrow S \cup \Bigl\{ \arg\max_{i \notin S} \; \min_{j \in S} d(i,j) \Bigr\}, \]

repeated until \(|S| = k\). This is the classical greedy heuristic for

\[ \max_{|S| = k} \; \min_{i \ne j \in S} d(i,j). \]

Guarantee: 2-approximation. Farthest-point traversal is guaranteed to reach at least half the optimal minimum separation, and no better ratio is achievable in polynomial time unless P = NP. In practice it usually lands far closer to optimal than the bound suggests.

Reference

At a glance
Guarantee 2-approximation (farthest-point traversal)
License BSD-3-Clause
Version 2026.3.4
Released 2026-07-16
Determinism seeded
Input a caller-supplied distance function
Source https://www.rdkit.org/docs/source/rdkit.SimDivFilters.rdSimDivPickers.html
Last verified 2026-07-27

Capabilities

Support: ✔ built in · ◐ reachable, but you supply the model, transform or metric · — not available

Capability Support Notes
distance metrics · L1 (Manhattan) distance ◐ 1
distance metrics · L2 (Euclidean) distance ◐ 1
distance metrics · cosine distance ◐ 1
distance metrics · caller-supplied distances ✔ 2
diversity objectives · maximize the minimum separation ✔
diversity objectives · maximize the mean nearest-neighbor separation —
diversity objectives · maximize the geometric-mean nearest-neighbor separation —
diversity objectives · maximize the mean pairwise distance —
constraints beyond k · per-group counts over disjoint groups — 3
constraints beyond k · per-group counts over overlapping groups —
constraints beyond k · minimum and maximum counts per group —
time budget · budget expressed as an iteration count —
time budget · budget expressed as wall-clock time —
time budget · the answer improves when given more budget — 4
largest practical problem size n ≈ 106 5

  1. Reachable through the distance callback you supply — RDKit itself has no opinion about the metric, it only calls your function. ↩↩↩

  2. The callback is the native interface rather than an escape hatch, which is why this picker scales further than any other tool here: it never needs all n² distances to exist at once. ↩

  3. No per-group counting of any kind. It does accept a set of items that must appear in the result, which is a different guarantee entirely: membership for named items, not proportions across groups. ↩

  4. A single construction pass, so there is no budget to spend: the answer is whatever one greedy sweep produces, and waiting longer does not change it. ↩

  5. The only tool here that never materializes a distance matrix: it calls your distance function lazily and keeps one running nearest-selected distance per candidate, so memory is O(n) and the ceiling is set by how fast your callback is rather than by n² storage. ↩