Feature-based Individual Fairness in k-Clustering
  Ensuring fairness in machine learning algorithms is a challenging and
important task. We consider the problem of clustering a set of points while
ensuring fairness constraints. While there have been several attempts to
capture group fairness in the k-clustering problem, fairness at an individual
level is not well-studied. We introduce a new notion of individual fairness in
k-clustering based on features that are not necessarily used for clustering. We
show that this problem is NP-hard and does not admit a constant factor
approximation. We then design a randomized algorithm that guarantees
approximation both in terms of minimizing the clustering distance objective as
well as individual fairness under natural restrictions on the distance metric
and fairness constraints. Finally, our experimental results validate that our
algorithm produces lower clustering costs compared to existing algorithms while
being competitive in individual fairness.
