A New Framework for Fair $k$-Median: Static and Dynamic

Concerns over bias in AI-driven decision-making have made fairness a prominent issue in machine learning. In this work, we study fair clustering under the $k$-median objective, following a popular notion of fairness suggested by Chierichetti et al., which requires each cluster to maintain a balanced representation of input classes. Building on the reduction of Chierichetti et al., which transforms fair $k$-median into its vanilla counterpart via fairlet decompositions, we give a general framework that converts any polynomial-time fairlet decomposition into almost-linear time algorithm with only a constant-factor loss in approximation. Through the extension of our framework, we obtain the first efficient dynamic algorithm for maintaining a fair decomposition under point insertions and deletions. We validate our algorithms on real-world datasets, demonstrating competitive performance against existing baselines.