  In the Non-Uniform $k$-Center problem, a generalization of the famous
$k$-center clustering problem, we want to cover the given set of points in a
metric space by finding a placement of balls with specified radii. In
$t$-NU$k$C Problem, we assume that the number of distinct radii is equal to
$t$, and we are allowed to use $k_i$ balls of radius $r_i$, for $1 \le i \le
t$. This problem was introduced by Chakrabarty et al. [ACM Trans. Alg.
16(4):46:1-46:19], who showed that a constant approximation for $t$-NU$k$C is
not possible if $t$ is unbounded. On the other hand, they gave a bicriteria
approximation that violates the number of allowed balls as well as the given
radii by a constant factor. They also conjectured that a constant approximation
for $t$-NU$k$C should be possible if $t$ is a fixed constant. Since then, there
has been steady progress towards resolving this conjecture -- currently, a
constant approximation for $3$-NU$k$C is known via the results of Chakrabarty
and Negahbani [IPCO 2021], and Jia et al. [To appear in SOSA 2022]. We push the
horizon by giving an $O(1)$-approximation for the Non-Uniform $k$-Center for
$4$ distinct types of radii. Our result is obtained via a novel combination of
tools and techniques from the $k$-center literature, which also demonstrates
that the different generalizations of $k$-center involving non-uniform radii,
and multiple coverage constraints (i.e., colorful $k$-center), are closely
interlinked with each other. We hope that our ideas will contribute towards a
deeper understanding of the $t$-NU$k$C problem, eventually bringing us closer
to the resolution of the CGK conjecture.
