A New Notion of Individually Fair Clustering: α-Equitable k-Center

Code

• github.com/chakrabarti/equitable_clustering
  OfficialIn papernone★ 0

Abstract

Clustering is a fundamental problem in unsupervised machine learning, and fair variants of it have recently received significant attention due to its societal implications. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point j has a set of other points S_j that it perceives as similar to itself, and it feels that it is fairly treated if the quality of service it receives in the solution is -close (in a multiplicative sense, for a given 1) to that of the points in S_j. We begin our study by answering questions regarding the structure of the problem, namely for what values of the problem is well-defined, and what the behavior of the Price of Fairness (PoF) for it is. For the well-defined region of , we provide efficient and easily-implementable approximation algorithms for the k-center objective, which in certain cases enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results.

Tasks

Reproductions