Subexponential algorithm improves fair clustering with continuous centers
Subexponential Parameterized Approximation for Group-Fair Euclidean $k$-Center
Data Structures and Algorithms
Summary
Clustering is about grouping data points so that similar ones stay together, but sometimes these groups need to be fair to different categories like colors or types. The authors study a version of this problem where points are in fixed dimensional space, and clusters must have certain proportions from each category. They design an algorithm that finds good clusters with centers that can be anywhere, not just on data points, running faster than previous methods when looking for many groups. Their method slightly relaxes fairness rules but keeps the cluster sizes close to optimal.
What this means in practice
- •For data engineers: Efficiently generate fair clusters with continuous centers in spatial datasets respecting group proportions.
- •For machine learning practitioners: Use improved approximation algorithms to build fair clustering models that handle fairness constraints without excessive computational cost.
Authors
Rudranarayan Kar, Diya Roy, Abhishek Sahu
Abstract
Clustering is a basic tool for grouping data into meaningful classes, but in many applications the resulting clusters must also respect the fairness conditions among different groups. We study this direction for the group-fair Euclidean $k$-center problem in fixed dimension, where the input points are partitioned into disjoint color classes, and every cluster must satisfy given lower and upper bounds on the fraction of each color. We give a separator-based recursive approximation algorithm for the continuous-center setting. The main idea is to first reduce the continuous search space to a finite candidate center set and then use the geometric sphere separators to break the instance into smaller subproblems. Our algorithm gives a bicriteria approximation: the clustering radius is within a factor of $(1+ε)$ of the optimum exactly fair solution, while the fairness bounds are relaxed only by a multiplicative factor. For fixed dimension, number of colors, and approximation parameters, the running time is polynomial in input size and subexponential in $k$. A recent IJCAI-ECAI2026 result gives a $(1+ε)$-approximation for group-fair $k$-center in bounded doubling metrics with running time $(k/ε)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. In the fixed-dimensional Euclidean setting considered here, we improve the dependence on $k$ to subexponential, while allowing continuous centers. The fairness guarantees of the two results are different: the previous work allows an additive fairness violation, whereas our algorithm uses a controlled multiplicative relaxation.