Diversity-aware clustering: Computational Complexity and Approximation
  Algorithms
Suhas Thejaswi Ameet Gadekar Bruno Ordozgoiti Aristides Gionis
In this work, we study diversity-aware clustering problems where the data
points are associated with multiple attributes resulting in intersecting
groups. A clustering solution need to ensure that a minimum number of cluster
centers are chosen from each group while simultaneously minimizing the
clustering objective, which can be either $k$-median, $k$-means or
$k$-supplier. We present parameterized approximation algorithms with
approximation ratios $1+ \frac{2}{e}$, $1+\frac{8}{e}$ and $3$ for
diversity-aware $k$-median, diversity-aware $k$-means and diversity-aware
$k$-supplier, respectively. The approximation ratios are tight assuming Gap-ETH
and FPT $\neq$ W[2]. For fair $k$-median and fair $k$-means with disjoint
faicility groups, we present parameterized approximation algorithm with
approximation ratios $1+\frac{2}{e}$ and $1+\frac{8}{e}$, respectively. For
fair $k$-supplier with disjoint facility groups, we present a polynomial-time
approximation algorithm with factor $3$, improving the previous best known
approximation ratio of factor $5$.