  We study a variant of classical clustering formulations in the context of
algorithmic fairness, known as diversity-aware clustering. In this variant we
are given a collection of facility subsets, and a solution must contain at
least a specified number of facilities from each subset while simultaneously
minimizing the clustering objective ($k$-median or $k$-means). We investigate
the fixed-parameter tractability of these problems and show several negative
hardness and inapproximability results, even when we afford exponential running
time with respect to some parameters.
  Motivated by these results we identify natural parameters of the problem, and
present fixed-parameter approximation algorithms with approximation ratios
$\big(1 + \frac{2}{e} +\epsilon \big)$ and $\big(1 + \frac{8}{e}+ \epsilon
\big)$ for diversity-aware $k$-median and diversity-aware $k$-means
respectively, and argue that these ratios are essentially tight assuming the
gap-exponential time hypothesis. We also present a simple and more practical
bicriteria approximation algorithm with better running time bounds. We finally
propose efficient and practical heuristics. We evaluate the scalability and
effectiveness of our methods in a wide variety of rigorously conducted
experiments, on both real and synthetic data.
