  There has been a recent surge of interest in incorporating fairness aspects
into classical clustering problems. Two recently introduced variants of the
$k$-Center problem in this spirit are Colorful $k$-Center, introduced by
Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the
Fair Robust $k$-Center problem introduced by Harris, Pensyl, Srinivasan, and
Trinh. To address fairness aspects, these models, compared to traditional
$k$-Center, include additional covering constraints. Prior approximation
results for these models require to relax some of the normally hard
constraints, like the number of centers to be opened or the involved covering
constraints, and therefore, only obtain constant-factor pseudo-approximations.
In this paper, we introduce a new approach to deal with such covering
constraints that leads to (true) approximations, including a $4$-approximation
for Colorful $k$-Center with constantly many colors---settling an open question
raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan---and a
$4$-approximation for Fair Robust $k$-Center, for which the existence of a
(true) constant-factor approximation was also open. We complement our results
by showing that if one allows an unbounded number of colors, then Colorful
$k$-Center admits no approximation algorithm with finite approximation
guarantee, assuming that $\mathrm{P} \neq \mathrm{NP}$. Moreover, under the
Exponential Time Hypothesis, the problem is inapproximable if the number of
colors grows faster than logarithmic in the size of the ground set.
