Linear Time Algorithms for Individually Fair k-means via Multi-Swap Local Search - Cui, Beirong; Feng, Qilong; Huang, Junyu (Proceedings of the AAAI Conference on Artificial Intelligence, 2026)
Fair clustering has attracted increased attention in recent years. In this work, we study the individually fair clustering problem in Euclidean space. While single-swap local search methods have achieved near-linear running time and constant approximation guarantees, their performance often depends on the aspect ratio of the dataset (the ratio between the diameter and the minimum interpoint distance of the dataset). How to apply multi-swap local search while obtaining linear running time with better approximation ratio is still a challenging task. To address this, we introduce a collaborative initialization framework for that integrates greedy with sampling techniques. This framework eliminates the dependence on the aspect ratio and produces a constant-factor bicriteria approximation in linear time. In contrast to the current state-of-the-art near-linear time algorithm, which requires a restrictive assumption about the relationship between optimal centers and cluster centroids, we propose a multi-swap local search algorithm that provides an improved approximation guarantee. Our method runs in linear time with high probability and does not rely on the aforementioned assumption. We validate our theoretical results through extensive experiments on both real-world and synthetic datasets, including large-scale benchmarks with up to 100 million points. Our empirical evaluation demonstrates superior performance in terms of clustering quality and computational efficiency, along with scalability under varying parameter settings.