A Scalable Algorithm for Individually Fair K-means Clustering

Code

• github.com/google-research/google-research/tree/master/individually_fair_clustering
  Officialjax★ 0

Abstract

We present a scalable algorithm for the individually fair (p, k)-clustering problem introduced by Jung et al. and Mahabadi et al. Given n points P in a metric space, let (x) for x P be the radius of the smallest ball around x containing at least n / k points. A clustering is then called individually fair if it has centers within distance (x) of x for each x P. While good approximation algorithms are known for this problem no efficient practical algorithms with good theoretical guarantees have been presented. We design the first fast local-search algorithm that runs in ~O(nk^2) time and obtains a bicriteria (O(1), 6) approximation. Then we show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.

Tasks

Reproductions