Fair clustering for data summarization picks $k$ representative points, called centers or suppliers, so that every data point lies close to some center. It must also include enough, but not too many, centers from each demographic group. When groups overlap, as when one person is both a woman and over sixty, the best known algorithms list every way of distributing the $k$ centers across "atomic" groups, meaning the distinct combinations of memberships. That list grows exponentially in both $k$ and the number of groups $t$. The same authors whose disjoint-group method summarizes ten million points in minutes name the overlapping, "web-scale" case as unsolved. This is a clean instance of a wider pattern: an algorithm that is tractable in theory, because its exponential cost is confined to a parameter, yet unusable in practice because that confined cost is astronomical.
This note proposes removing the enumeration rather than speeding it up. For each guessed radius, the overlapping-group feasibility test in the tight 3-approximation can be written as a single integer program. Its core is a bipartite matching, which linear programming already solves exactly. On top of that core sit only $2t$ extra inequalities, one lower and one upper bound per group. The combinatorial difficulty then lives entirely in those few extra rows, not in $k$ or in the number of atomic groups. We also expect it to be small on real demographic data, and we propose to prove a structural result that makes this precise, build the solver, and measure the parameter that actually governs running time.
Core Claim
Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights gives a tight 3-approximation for fair $k$-supplier, the problem of choosing $k$ suppliers to minimize the largest client-to-supplier distance. For a guessed radius $r$, it first picks well-separated client representatives by farthest-first traversal. It then matches representatives to nearby suppliers subject to the group quotas. With disjoint groups this check is polynomial. With intersecting groups the authors enumerate multisets of atomic groups and solve one disjoint instance per multiset.
Our observation is that the per-radius check never needed the enumeration. Let $x_s \in \{0,1\}$ indicate that supplier $s$ is opened, and let $y_{cs}$ indicate that representative $c$ is served by $s$, where $s$ must lie within distance $r$ of $c$. Let $G_j$ be the suppliers in group $j$, with bounds $L_j$ and $U_j$. The feasibility test is
$$\sum_s y_{cs} = 1 \;\; \forall c, \qquad \sum_c y_{cs} \le x_s \;\; \forall s, \qquad \sum_s x_s = k, \qquad L_j \le \sum_{s \in G_j} x_s \le U_j \;\; \forall j \le t.$$
Without the last line this is a bipartite assignment with a cardinality constraint. Its constraint matrix is totally unimodular, meaning every vertex of its linear relaxation is integral. The overlapping groups add exactly $2t$ rows with 0/1 coefficients.
This reformulation preserves the 3-approximation guarantee. When $r$ is at least the optimal radius, the optimal solution induces a feasible integer point by the same argument the original paper uses, so solving this program exactly is a drop-in replacement for the multiset loop.
The theoretical handle is a face-dimension argument. A vertex of the relaxed program lies on a face of the matching-plus-cardinality polytope whose dimension is at most the number of tight side constraints, which is at most $t$. For bipartite matching, that face is spanned by at most $t$ alternating cycles or paths. So the fractional part of any optimal vertex decomposes into at most $t$ "swap moves," each exchanging some suppliers for others along a cycle.
We will turn this into two results. The first is an exact branch-and-bound procedure that branches on swap moves rather than on variables. We will characterize when its tree size depends only on $t$ and the number of atomic groups touched by the moves, and not on $k$ or $n$. The second is a rounding that violates each group bound by an amount controlled by the length and group composition of the at most $t$ moves.
Hardness constrains how far this can go. Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms shows a related capacitated problem is inapproximable in polynomial time even with $t$ logarithmic. Multiwinner Voting with Fairness Constraints shows that mere feasibility is NP-hard once candidates belong to three or more overlapping groups. Some exponential dependence on $t$ is therefore unavoidable. Our claim is that it should be the only exponential dependence, and that on real demographic data the number of tight overlapping constraints at the relaxation optimum is far below $t$.
Research Program
The theoretical part has three pieces. We will prove the swap-move structure lemma for the program above, including its generalization to suppliers grouped by atomic type.
We will then determine what parameter makes exact solving fixed-parameter tractable, meaning running in time $f(\cdot)\cdot n^{O(1)}$. The candidates are $t$ alone, $t$ plus the number of distinct atomic groups appearing in the representatives' neighborhoods, or $t$ plus maximum cycle length. Where exactness fails, we will give an explicit additive-violation rounding.
Two nearby results position this work. The complexity landscape of decompositional parameters for ILP maps when integer programs are tractable via treedepth plus bounded coefficients. Our matrix does not fit that map: the matching core has unbounded treedepth, and tractability comes instead from total unimodularity plus few dense rows. Parameterized Algorithms for Optimal Refugee Resettlement compresses interchangeable families into homogeneous blocks before invoking heavy block-structured integer programming. We reuse the compression idea, aggregating suppliers by atomic type within each representative's neighborhood, but avoid the heavy machinery whose hidden constants that paper's open problems flag.
The systems part implements the solver with a warm-started relaxation across binary search over radii, and branching on swap moves. The analysis part records, for every instance, the "effective parameter": how many side constraints are tight and how many swap moves are fractional at the relaxation optimum. Running time can then be explained by a measured quantity rather than by the worst-case bound.
As a second test of the same mechanism, we will apply it to committee selection with overlapping quotas. That problem is the matching-free special case, a cardinality constraint plus $2t$ rows, where Multiwinner Voting with Fairness Constraints gives up exact feasibility and accepts bounded quota violations.
Baselines
The naive reference point is the brute-force exact approach. Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms reports it "failed to process even 80 points." We also include the unconstrained 3-approximation followed by repair, which shows how often naive repair fails to restore feasibility.
The strongest directly comparable method is the atomic-multiset enumeration of Fair Clustering for Data Summarization. It is the published algorithm with the same guarantee on the same problem. The reported figure is for the disjoint-group version: "10 million data points in under 5 minutes," with a proven factor of 3. No reported result was found on Lacuna for the runtime of its intersecting-group variant.
We will reimplement that variant in the same language. It will use the same farthest-first representatives, the same radius search and the same matching code, on identical hardware with identical time limits. The only difference between the two systems is then the replacement of the multiset loop by our integer program. Beating it means solving instances with larger $t$ and $k$ within the time limit at equal radius, since both methods are exact for the same test.
Two further baselines come from Capacitated Fair-Range Clustering and Clustering with Fair-Center Representation. The first is the tree-embedding dynamic program, which "solved real-world instances with n ≈ 700 points and k = 10 centers in under 10 minutes," with an empirical ratio "below 2.7" on synthetic data. The second is the local-search heuristic LS1, which has no proven ratio. Both receive the same time budget and are scored on radius, feasibility rate and wall-clock time.
The key ablation hands our exact program, unchanged, to a commercial mixed-integer solver with default branching. This isolates whether swap-move branching matters or whether the reformulation alone does the work.
Why not just…?
Why not just give the whole fair $k$-supplier problem to Gurobi? This is a real threat, and our method is itself a structured integer program. The difference is size and shape. The full exact formulation optimizes the radius over all client-supplier assignments. Ours fixes the radius and works only on at most $k$ representatives, leaving a matching core plus $2t$ rows. The complexity landscape of decompositional parameters for ILP shows general integer programs stay hard even at treewidth 3, so solver success must come from structure. We will run the full formulation, the reduced formulation under default Gurobi, and the reduced formulation under our branching. If default Gurobi on the reduced program matches us, we will report that the contribution is the reduction and the effective-parameter analysis, not the branching rule.
Why not just use local search or LP rounding with bounded quota violations? Clustering with Fair-Center Representation finds LS1 often feasible but without guarantees. Multiwinner Voting with Fairness Constraints and Proportionally Fair Matching via Randomized Rounding accept quota violations or merely probabilistic fairness. Our experiments report how often these heuristics end infeasible, and by how much they exceed quotas, on instances where our solver certifies a feasible point. If they are nearly always exactly feasible at equal radius, the case for exactness weakens, and we will say so.
Why not just enforce each attribute's quotas separately? Bounding and Approximating Intersectional Fairness through Marginal Fairness shows marginal quantities match intersectional ones only under independence, and its Total Correlation bounds are loose in practice. Note also that the group constraints here already are per group. The cost of overlap comes from the fact that one chosen center moves several counters at once, so separate per-attribute solving simply does not produce a feasible answer. We will quantify how often its output violates the overlapping bounds.
Proposed Experiments
We will use the UCI datasets used by the clustering papers above: Heart, Census, Dutch-Census, Credit-card, bank-full, the student datasets and NPHA. To push $t$ beyond what those papers test, we add point data built from the Folktables American Community Survey tasks used in Intersectional Fairness via Mixed-Integer Optimization and the roughly 2.4-million-sample 1990 Census with 8 protected attributes from Bounding and Approximating Intersectional Fairness through Marginal Fairness. Groups are formed from binned race, sex, age, disability and region. We also generate synthetic sets up to ten million points with controlled attribute correlation.
The decisive scaling check sweeps $t$ from 2 to around 30 and $k$ from 5 to 100. It records runtime, branch-and-bound nodes, and the measured count of tight side constraints and fractional swap moves.
The claim survives if node counts track the measured effective parameter and stay flat in $k$ and in the number of atomic groups. It fails if nodes grow with $k$, or with the number of atomic groups, the way multiset enumeration does. A second check plants correlated "adversarial" group structures, borrowing the worst-case construction idea from the Dirichlet experiments of Molina and Loiseau. Its purpose is to find where the effective parameter blows up and to confirm that the predicted hardness appears exactly there.
For committee selection, we use the 400-voter, 120-candidate spatial simulation of Multiwinner Voting with Fairness Constraints. There, constrained rules reached "100% of the optimal unconstrained score" with Gini index zero. We increase the overlap degree to three or more groups per candidate and test whether exact feasibility is attainable in seconds where that work settles for bounded violations.
References
- Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights
- Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
- Multiwinner Voting with Fairness Constraints
- The Complexity Landscape of Decompositional Parameters for ILP
- Parameterized Algorithms for Optimal Refugee Resettlement
- Clustering with Fair-Center Representation: Parameterized Approximation Algorithms and Heuristics
- Proportionally Fair Matching via Randomized Rounding
- Bounding and Approximating Intersectional Fairness through Marginal Fairness
- Intersectional Fairness via Mixed-Integer Optimization