Skip to content

Comparison with Other Tools

How does max-div relate to other freely available tools that select diverse subsets? The honest answer starts with recognizing that the alternatives fall into three different categories, and a flat ranking across them would be misleading:

  • Exact solvers (SCIP, OR-Tools CP-SAT, HiGHS) are general MIP/CP engines. Given a hand-built model they prove optimality — but only at small problem sizes, at minutes-to-hours cost. They are best read as the optimality reference, not as competitors.
  • One-shot pickers & samplers (RDKit, skmatter, fpsample, apricot, qc-selector, DPPy) run a single-shot construction: one pass, one answer, typically in milliseconds. Very fast, but the answer does not improve if you can afford more time, and none of them supports general per-group selection constraints.
  • Anytime heuristic optimizers — max-div's category: start from a construction, then keep improving the selection for as long as the time budget allows, under fairness constraints if given.

The tables below make those categories explicit. Terminology for the objective columns is defined in Objectives & the Diversity-Problem Landscape, and each tool's name links to its profile, where the same capabilities are laid out one tool at a time with the reasoning behind every mark.

Tool distance metrics diversity objectives constraints beyond k time budget max practical n
L1 L2 cosine custom max-min mean-of-NN geomean-of-NN max-sum disjoint groups overlapping groups ranged counts iterations wall clock improves with budget
Anytime optimizers
max-div ✔ ✔ ✔ ✔1 ✔ ✔ ✔ ✔ ✔ ✔ ✔2 ✔ ✔ ✔ n ≈ 104–1053
Exact solvers
OR-Tools CP-SAT ◐4 ◐4 ◐4 ✔5 ◐6 ◐7 ◐7 ◐7 ◐8 ◐8 ◐8 ✔ ✔ ◐9 n ≈ 10310
SCIP (PySCIPOpt) ◐11 ◐11 ◐11 ✔12 ◐13 ◐14 ◐14 ◐13 ◐8 ◐8 ◐8 ✔ ✔ ◐9 n ≈ 10315
HiGHS ◐11 ◐11 ◐11 ✔16 ◐13 ◐14 ◐14 ◐13 ◐8 ◐8 ◐8 ✔ ✔ ◐9 n ≈ 10317
One-shot pickers & samplers
RDKit MaxMinPicker ◐18 ◐18 ◐18 ✔19 ✔ — — — —20 — — — — —21 n ≈ 10622
fpsample — ✔ ◐23 —24 ✔ — — — — — — — — —21 n ≈ 10625
skmatter — ✔ ◐23 — ✔ — — — — — — — — —21 n ≈ 10526
apricot-select ✔ ✔ ✔ ✔27 —28 —28 —28 ✔29 — — — — — —21 n ≈ 10530
qc-selector ✔ ✔ ◐23 ✔31 ✔ —32 —32 ✔ ✔33 — — ◐34 — —21 n ≈ 10435
DPPy ◐36 ◐36 ◐36 ✔37 —38 —38 —38 —38 — — — ◐39 — — n ≈ 10440
code-FDM ◐41 ✔ ◐41 ✔42 ✔ — — — ✔43 —44 —45 — — —21 n ≈ 10446

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

Tool Guarantee License Version Released Determinism Input Last verified
Anytime optimizers
max-div heuristic Apache-2.0 0.8.3 2026-07-27 seeded, fully reproducible vectors (L1 / L2 / L2² / cosine) or a precomputed distance matrix 2026-07-27
Exact solvers
OR-Tools CP-SAT proven optimum Apache-2.0 9.15.6755 2026-01-14 deterministic with a fixed worker count a hand-built model 2026-07-27
SCIP (PySCIPOpt) proven optimum Apache-2.0 (SCIP)47 6.2.1 2026-05-16 deterministic a hand-built model 2026-07-27
HiGHS proven optimum MIT 1.15.1 2026-07-02 deterministic a hand-built model 2026-07-27
One-shot pickers & samplers
RDKit MaxMinPicker 2-approximation (farthest-point traversal) BSD-3-Clause 2026.3.4 2026-07-16 seeded a caller-supplied distance function 2026-07-27
fpsample 2-approximation (farthest-point traversal) MIT 1.0.2 2025-12-20 deterministic vectors 2026-07-27
skmatter 2-approximation (farthest-point traversal) BSD-3-Clause 0.3.3 2026-01-06 deterministic vectors 2026-07-27
apricot-select 1−1/e (lazy greedy on a monotone submodular function) MIT 0.6.1 2021-02-1848 deterministic vectors or a precomputed similarity matrix 2026-07-27
qc-selector heuristic GPL-3.0 0.1.4 2026-02-03 seeded vectors or a distance matrix 2026-07-27
DPPy sampler, not optimizer MIT 0.3.3 2024-08-14 seeded sampling a similarity kernel matrix 2026-07-27
code-FDM heuristic with approximation bounds stated in the paper none declared — —49 not documented vectors 2026-07-27

Every fact above was verified on or after 2026-07-27; each tool's own date is in the table.

What the table means in practice

  • If you need a proven optimum (and your problem is small): build a MIP/CP model — CP-SAT for max-min, SCIP for the mean-of-NN objectives. max-div cannot prove optimality.
  • If you need one diverse subset as fast as possible, unconstrained: greedy FPS (fpsample, skmatter, RDKit) is excellent — within a factor 2 of the max-min optimum, in milliseconds.
  • If you can spend more than milliseconds, want NN-separation or max-sum objectives beyond max-min, or have per-group selection constraints: this is max-div's territory. General min/max per-group counts are supported by none of the pickers (code-FDM comes closest, for max-min only), and the mean/geomean-of-NN objectives are — as far as we know — implemented nowhere else.

Notable omission: submodlib (a submodular-optimization zoo including disparity-min, i.e. max-min) currently cannot be installed on Python 3.13 (no wheels or sdist for it on PyPI as of the verification dates above) and is therefore listed here only as a mention.

  1. A problem can be built from a precomputed distance matrix, square or condensed, so any metric the caller can compute is usable without max-div implementing it. ↩

  2. Counts are per-group minimum and maximum bounds, and carry per-constraint weights and a choice of linear or quadratic penalty shaping when a problem is over-constrained. ↩

  3. Bounded by the pairwise distance matrix, which is materialized once at O(n²)/2 float32 entries; beyond n ≈ 10⁵ that no longer fits comfortably in memory. The solver itself is anytime, so the practical ceiling is memory rather than time. ↩

  4. Reachable, but CP-SAT is an integer solver: distances must be scaled to integers before they enter the model, so the achievable precision is a modelling choice rather than a property of the metric. ↩↩↩

  5. Any distance you can compute and round to integers is usable, which in practice means any metric at all. ↩

  6. Reachable through a threshold feasibility search: ask whether a selection exists with every pair at least t apart, then binary-search t. It is a natural fit for CP-SAT and the reason this solver appears here at all. ↩

  7. No natural constraint-programming encoding. Expressing a nearest-neighbor mean needs the same auxiliary assignment structure a MILP would use, at which point a MILP solver is the better tool. ↩↩↩

  8. Reachable as linear constraints over the selection variables, which you write yourself. Any counting constraint expressible that way is available. ↩↩↩↩↩↩↩↩↩

  9. The incumbent improves as the branch-and-bound search proceeds, but that is a proof search rather than an anytime budget: progress is uneven, and time spent may go entirely into tightening the bound rather than improving the solution. ↩↩↩

  10. Max-min is solved by repeatedly asking a feasibility question — "can k items all be at least t apart?" — and each question is a fresh constraint-propagation search over O(n²) pairwise constraints. That stays tractable to around n ≈ 10³ and degrades sharply beyond it. ↩

  11. Reachable, but you build the model: distances enter as precomputed objective coefficients, so the metric is whatever you computed before the solver ever sees it. ↩↩↩↩↩↩

  12. Since every distance is a coefficient you supply, an arbitrary metric costs nothing extra — this is the one distance axis where a modelling solver is at no disadvantage. ↩

  13. Reachable, but the objective must be linearized by hand — for max-min, a threshold variable bounded below every selected pair via big-M constraints. ↩↩↩↩

  14. Reachable only through an assignment MILP that pairs each selected item with its nearest selected neighbor; the formulation is considerably larger than the max-min one and is what drives the practical size limit down. ↩↩↩↩

  15. The limit differs sharply by objective. A max-min model with big-M linearization is routinely solved to optimality around n ≈ 10³; the mean-of-NN objective needs an assignment MILP whose size grows far faster and which stops being tractable near n ≈ 60 — below the floor of the benchmark generators used here. The single value reported is the max-min one, because that is the formulation this comparison actually exercises. ↩

  16. Distances are coefficients you supply, so an unusual metric costs no more than a common one. ↩

  17. The same big-M max-min formulation SCIP solves, and the same ceiling: the model carries a constraint per pair, so it grows quadratically and stops closing the gap in reasonable time around n ≈ 10³. ↩

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

  19. 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. ↩

  20. 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. ↩

  21. 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. ↩↩↩↩↩↩

  22. 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. ↩

  23. Reachable by L2-normalizing the vectors first: on the unit sphere, cosine distance is a monotone function of Euclidean distance, so a Euclidean picker returns the same ordering. ↩↩↩

  24. Euclidean only. The KD-tree variants depend on it structurally, so this is not a gap waiting to be filled. ↩

  25. A Rust implementation with KD-tree accelerated variants, so the traversal avoids the O(nk) distance evaluations a naive sweep needs. The tree variants degrade in high dimension and are documented as practical below roughly d ≈ 9; the plain variant has no such limit. ↩

  26. A NumPy implementation following scikit-learn conventions: no distance matrix is stored, but each pick scans all remaining candidates, so cost grows as n·k. Comfortable into the hundreds of thousands, an order below the compiled implementations. ↩

  27. A precomputed similarity matrix is a first-class input, so any similarity you can compute is usable. Note the sign convention: apricot maximizes similarity coverage, so a distance has to be turned into a similarity first. ↩

  28. Submodular coverage objectives, not dispersion ones. Nothing here maximizes a minimum separation, and no reformulation makes facility location do so. ↩↩↩

  29. Facility location rewards how well the selection covers the remaining items, which on a distance-derived kernel is the standard submodular surrogate for a max-sum style objective — related to, but not identical with, maximizing the mean pairwise distance. ↩

  30. Facility location needs an n × n similarity matrix unless you supply a sparse one, which puts the ceiling where any quadratic-memory method's sits. Its lazy and stochastic greedy variants cut the number of function evaluations, not the storage. ↩

  31. A precomputed distance matrix is accepted directly, so any metric you can compute is usable. ↩

  32. Its diversity measures are computed over the whole selection rather than over nearest-neighbor pairs, so the nearest-neighbor family is absent. ↩↩

  33. Label-stratified selection: given class labels, it picks proportionally across them. That covers disjoint groups with proportional targets, but not arbitrary minimum and maximum counts, and not groups an item can belong to more than once. ↩

  34. Several of its methods take a parameter that controls how much work they do — a sphere-exclusion radius, an OptiSim subsample size — but these change the character of the search rather than lengthening it. Raising one does not mean a better answer. ↩

  35. Its selection methods work from a full distance matrix, and the diversity measures it offers are computed over that matrix rather than incrementally, so both memory and per-pick cost are quadratic. Comfortable in the tens of thousands. ↩

  36. Reachable only through the kernel you supply. DPPy never sees vectors or a distance function: you choose how similarity is defined when you build the kernel, and any metric you can express that way is available. ↩↩↩

  37. The kernel is entirely caller-supplied, so a custom similarity is the native case rather than a workaround. Note the sign convention differs from a distance: the kernel encodes similarity, and diversity comes from its determinant being large. ↩

  38. DPPy draws samples from a determinantal point process rather than maximizing anything. Diversity is a property of the distribution it samples from — subsets whose kernel submatrix has a large determinant are more likely — so no objective is optimized and no selection is claimed to be best. ↩↩↩↩

  39. You can ask for more samples, but a sample count is a number of independent draws, not an improvement budget — the tenth draw is no better than the first, merely different. ↩

  40. An n × n kernel matrix must be materialized, and exact k-DPP sampling eigendecomposes it — an O(n³) step that dominates well before memory does. Around n ≈ 10⁴ that is still minutes; beyond it, approximate samplers are the only route. ↩

  41. The implementation is written around Euclidean distance; another metric means editing the source rather than passing an argument. ↩↩

  42. Since you are editing the source in any case, an arbitrary metric is no harder than a common one — a consequence of it being research code rather than a designed feature. ↩

  43. This is the whole point of the tool: it selects a maximally dispersed subset subject to a required count from each group, which is the fair-diversity problem max-div also targets. ↩

  44. Each item belongs to exactly one group. Overlapping membership — an item that is both in-region and in-category — is outside the model the algorithms are built on. ↩

  45. Counts are exact requirements per group, not a minimum and a maximum, so a range cannot be expressed. ↩

  46. Research code built around a full distance matrix and repeated threshold scans over it. No effort has gone into constant factors, so the practical ceiling sits below the maintained libraries at comparable memory. ↩

  47. The two halves carry different licenses: the SCIP solver itself is Apache-2.0, while the PySCIPOpt binding installed from PyPI is MIT. Source ↩

  48. The PyPI release is from 2021, but the project is not abandoned: its repository was last updated in November 2025. Installing from PyPI gets you considerably older code than the repository holds. Source ↩

  49. Never packaged: this is a research repository, not a release. Its last commit was in July 2022 and it carries no license file, which means no permission to use it is granted — a blocker for anything beyond reading the code, regardless of how well it performs. Source ↩