Proportionally Fair Clustering

We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering npoints with kcenters, we define fairness as proportionality to mean that any n/kpoints are entitled to form their own cluster if there is another center that is closer in distance for all n/kpoints. We seek clustering solutions to which there are no such justified complaints from any...