Introduction
Standard clustering objectives, such as $k$-center or $k$-means, focus on minimizing global error metrics. However, these objectives often neglect individual fairness, potentially placing points in sparse regions at a significant disadvantage. Individually fair clustering aims to ensure that every point is served by a center within a distance proportional to its local density. This paper introduces the first subquadratic-time approximation algorithms for the individually fair $k$-center problem, addressing the computational bottleneck inherent in previous $O(n^2)$ approaches.
Problem Definition
Individual fairness in clustering posits that if a dataset $P$ of $n$ points is partitioned into $k$ clusters, each cluster "on average" represents $n/k$ points. Consequently, every point $x \in P$ should have a center within its "fairness radius" $r_x$, defined as the distance to its $\lceil n/k \rceil$-th nearest neighbor.
Finding an optimal fair clustering is NP-hard. Moreover, simply calculating the fairness radii for all $n$ points requires $O(n^2)$ time, which is prohibitive for massive datasets. The goal of this work is to provide $(\beta, \gamma)$-bicriteria approximations—where points are within $\beta \cdot r_x$ of a center and the total cost is at most $\gamma$ times the optimal—while breaking the quadratic time complexity barrier.
Methodology
The authors propose two primary algorithmic frameworks to achieve these goals:
1. Deterministic $(2, 2)$-Bicriteria Approximation
This algorithm improves upon previous $(3, 3)$-approximations. It operates in $O(n^2 + kn \log n)$ time by sorting points by their fairness radii and greedily selecting centers that maintain a minimum separation distance.
2. Randomized Subquadratic Approximation
To overcome the $O(n^2)$ bottleneck, the authors introduce a randomized sampling procedure called FairSampling. Instead of computing exact fairness radii, the algorithm estimates them by sampling a small subset of the data.
As shown in Algorithm 4, the procedure selects a subset $S$ of size $s \approx O(k \ln(n/\delta))$ and uses the distance to the $t$-th nearest neighbor in $S$ to approximate the true fairness radius. This estimation, combined with a pruned set of cost candidates generated via Gonzalez’s algorithm, allows for a $(10, 2 + \epsilon)$-approximation in $O(nk \log(n/\delta) + k^2/\epsilon)$ time.
Key Results
The theoretical analysis demonstrates significant improvements over the state-of-the-art:
- Efficiency: For large-scale datasets where $k \ll n$, the randomized algorithm reduces complexity from quadratic to near-linear in $n$.
- Robustness: The
FairSampling(orApproxFairRadii) procedure is a standalone contribution that can be integrated into other fair clustering problems, such as $k$-median or $k$-means. - Theoretical Guarantees: The deterministic algorithm provides a tight $(2, 2)$-approximation, while the randomized version maintains a constant-factor approximation even with significantly reduced computation.
Conclusion and Future Work
This work provides a critical step toward making individually fair clustering practical for large datasets. By relaxing the fairness and cost constraints slightly, the authors achieve a massive jump in algorithmic speed. Future research may focus on tightening the approximation constants (currently 10 for the randomized version) and empirically evaluating these algorithms on real-world fairness benchmarks.
Summary updated