r-Gather: Minimum-Size Clustering

An implementation and experimental study of the r-gather (minimum-size) clustering problem: given n points in a metric space and an integer r, partition the points into clusters so that every cluster has at least r points while minimising the maximum cluster radius (the largest distance from a cluster's centre to any of its members).

The problem is NP-complete and cannot be approximated within any factor better than 2 unless P = NP. This repository provides:

• a complete implementation of the classical 2-approximation algorithm (Aggarwal et al., Achieving Anonymity via Clustering, ACM TALG 2010);
• two output-preserving accelerations of it (binary search over candidate radii; a grid-based neighbourhood test);
• a faster sampling-based divide-and-conquer algorithm that trades the approximation guarantee for speed;
• a benchmarking and experiment suite that compares them on running time and solution quality.

Algorithms

Original 2-approximation

A threshold-search algorithm over O(n²) candidate radii R = d(p_i, p_j)/2, examined in increasing order. For each R it runs a feasibility test:

• Condition 1 — every point has at least r points (including itself) within distance 2R.
• Condition 2 — a greedy phase picks cluster centres (marking everything within 2R of each centre), then a maximum-flow network checks that each centre can be assigned r distinct points (source → centre capacity r, centre → point capacity 1 when within 2R, point → sink capacity 1).

The first R passing both conditions yields clusters of radius ≤ 2R ≤ 2·OPT. The maximum-flow feasibility test is the dominant cost.

Output-preserving accelerations

• Binary search over the candidate radii (feasibility is monotone in R), reducing the number of feasibility tests to O(log n).
• Grid-based Condition 1, bucketing points into cells of side 2R and inspecting only adjacent cells (O(n) per radius instead of O(n²)).

Both return exactly the same clustering as the original algorithm.

Sampling-based divide-and-conquer

A faster algorithm that gives up the 2-approximation guarantee:

1. Sample and cluster — draw a random half-sized sample S, and run r'-gather on it with a halved parameter r' = ⌈r/2⌉, obtaining sub-clusters C1 and a radius R.
2. Absorb and re-cluster — absorb the non-sampled points that fall inside the 2R disks of C1; run r'-gather on the uncovered remainder to get C2.
3. Merge — because every sub-cluster has ≥ ⌈r/2⌉ points, two of them always reach r. The default matching merge pairs each under-sized sub-cluster with a nearby one within 2R, while heavy (≥ r) sub-clusters stand alone, producing final clusters of size ≥ r.

The entry point is divide_conquer_r_gather(points, r).

Repository layout

r_gather/                 # the algorithm package
  data_structures.py      # Point, Cluster
  distance_matrix.py      # pairwise distance matrix
  conditions.py           # Condition 1 (standard + grid)
  clustering.py           # greedy initial clustering + cluster construction
  flow_network.py         # max-flow feasibility (NetworkX + Dinic) and merges
  radius_search.py        # sequential / binary radius search strategies
  core.py                 # compute_r_gather: pluggable entry point
  divide_conquer.py       # divide_conquer_r_gather + recursive prototype
tests/                    # correctness tests + experiment/plot scripts

compute_r_gather is fully dependency-injected: the radius search, Condition 1 test, flow verification, initial clustering, and cluster construction are all swappable arguments, so a variant is a different set of keyword arguments rather than a forked code path (see tests/test_variants.py).

Environment

Requires Python ≥ 3.10. Dependencies are managed with uv.

• Core algorithm: numpy, networkx, matplotlib.
• dev extra: pytest (test suite).
• experiments extra: scipy (only the exact-optimum MILP solver uses it; the core algorithm never imports it).

uv sync --extra dev --extra experiments

Running the tests

uv run --extra dev --extra experiments python -m pytest -q

Running the experiments

All experiment scripts write to output/<name>/<run>/. Recording and plotting are separate steps; every recorder accepts --quick for a fast smoke run.

Runtime benchmark (scaling in n and r)

uv run python -m tests.test_benchmark_suite            # full sweep -> CSV + plots + summary
uv run python -m tests.test_benchmark_suite --quick    # ~30s smoke run

Approximation ratio against the exact optimum

The exact optimum on small instances is computed with a mixed-integer program (HiGHS via scipy).

uv run --extra experiments python -m tests.experiment_opt_ratio   # record
uv run --extra experiments python -m tests.plot_opt_ratio         # plot newest run

Scaling with fitted growth exponents

Supported datasets: uniform, gaussian (Gaussian mixture), geonames (real city coordinates, Europe), geonames_na (North America). The GeoNames data is downloaded once and cached under output/datasets/.

uv run --extra experiments python -m tests.experiment_scaling --dataset uniform    # record
uv run --extra experiments python -m tests.experiment_scaling --dataset geonames   # record
uv run --extra experiments python -m tests.plot_scaling                            # plot newest run
uv run --extra experiments python -m tests.plot_datasets_compare                   # cross-dataset radius figure

Design experiments

# Recursive divide-and-conquer prototype
uv run --extra experiments python -m tests.experiment_recursive --out output/recursive/run
uv run --extra experiments python -m tests.plot_recursive output/recursive/run

# Ablation of the design choices (sample ratio, r', absorption step)
uv run --extra experiments python -m tests.experiment_ablation --out output/ablation/run
uv run --extra experiments python -m tests.plot_ablation output/ablation/run

# Merge-strategy and grid-acceleration matrix
uv run --extra experiments python -m tests.experiment_merge_matrix --out output/merge_matrix/run
uv run --extra experiments python -m tests.plot_merge_matrix output/merge_matrix/run

License

Distributed under the terms of the GNU Affero General Public License v3.0. See LICENSE.