Skip to content

code-FDM

code-FDM is the reference implementation accompanying published work on fair diversity maximization — max-min selection subject to a required number of items from each group. It is the only surveyed tool besides max-div that treats group constraints as part of the problem rather than as post-processing.

That makes it the closest comparison point for max-div's fairness constraints, and the differences are instructive. Its groups partition the items, so each item belongs to exactly one; max-div's may overlap. Its counts are exact requirements; max-div's are minimum and maximum bounds. And it is a construction algorithm, so it produces one answer rather than improving one.

Before considering it for anything beyond reading: it carries no license. No permission to use, copy or modify it has been granted, which is a legal question rather than a technical one. Its last commit was July 2022.

Problem targeted

Given \(n\) items partitioned into groups \(G_1,\dots,G_m\), a distance \(d(i,j)\), and a required count \(k_g\) for each group, it targets

\[ \max_{S} \; \min_{i \ne j \in S} d(i,j) \qquad\text{subject to}\qquad |S \cap G_g| = k_g \;\; \forall\, g . \]

The algorithms proceed by fixing a candidate threshold, building the graph of pairs closer than it, and searching for a group-feasible independent set — then adjusting the threshold.

Guarantee: heuristic, with bounds stated in the accompanying paper for particular variants. The implementation is a research artifact, so treat published ratios as claims about the algorithms rather than about this code.

Reference

At a glance
Guarantee heuristic with approximation bounds stated in the paper
License none declared
Version —
Released — 1
Determinism not documented
Input vectors
Source https://github.com/yhwang1990/code-FDM
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 ◐ 2
distance metrics · L2 (Euclidean) distance ✔
distance metrics · cosine distance ◐ 2
distance metrics · caller-supplied distances ✔ 3
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 ✔ 4
constraints beyond k · per-group counts over overlapping groups — 5
constraints beyond k · minimum and maximum counts per group — 6
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 — 7
largest practical problem size n ≈ 104 8

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

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

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

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

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

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

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

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