Skip to content

apricot-select

apricot maximizes submodular functions, most usefully facility location: pick the subset that best represents everything you did not pick. That is a coverage objective, and it is worth being precise that coverage and dispersion are not the same goal.

A dispersion objective asks that selected items be far from each other. A coverage objective asks that unselected items be close to something selected. The two often agree — a well-spread selection covers well — but they can diverge, and apricot optimizes the second.

What it brings in exchange is a real approximation guarantee. Greedy maximization of a monotone submodular function is within \(1 - 1/e\) of optimal, which is a stronger statement than any heuristic here can make, on an objective that is genuinely different.

Problem targeted

Given \(n\) items and a similarity \(s(i,j)\), facility location selects

\[ \max_{S \subseteq \{1,\dots,n\},\; |S| = k} \;\sum_{i=1}^{n} \max_{j \in S} \, s(i,j). \]

Each unselected item contributes its similarity to whichever selected item represents it best, so the objective rewards a selection that leaves nothing far from everything.

Guarantee: \(1 - 1/e\). The function is monotone and submodular, so greedy maximization is within a factor \(1 - 1/e \approx 0.63\) of optimal — a bound that holds for this objective, not for the dispersion objectives the other tools target.

Reference

At a glance
Guarantee 1−1/e (lazy greedy on a monotone submodular function)
License MIT
Version 0.6.1
Released 2021-02-18 1
Determinism deterministic
Input vectors or a precomputed similarity matrix
Source https://apricot-select.readthedocs.io/
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 ✔
distance metrics · L2 (Euclidean) distance ✔
distance metrics · cosine distance ✔
distance metrics · caller-supplied distances ✔ 2
diversity objectives · maximize the minimum separation — 3
diversity objectives · maximize the mean nearest-neighbor separation — 3
diversity objectives · maximize the geometric-mean nearest-neighbor separation — 3
diversity objectives · maximize the mean pairwise distance ✔ 4
constraints beyond k · per-group counts over disjoint groups —
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 — 5
largest practical problem size n ≈ 105 6

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

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

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

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

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

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