  In this paper, we introduce and study the Non-Uniform k-Center problem
(NUkC). Given a finite metric space $(X,d)$ and a collection of balls of radii
$\{r_1\geq \cdots \ge r_k\}$, the NUkC problem is to find a placement of their
centers on the metric space and find the minimum dilation $\alpha$, such that
the union of balls of radius $\alpha\cdot r_i$ around the $i$th center covers
all the points in $X$. This problem naturally arises as a min-max vehicle
routing problem with fleets of different speeds.
  The NUkC problem generalizes the classic $k$-center problem when all the $k$
radii are the same (which can be assumed to be $1$ after scaling). It also
generalizes the $k$-center with outliers (kCwO) problem when there are $k$
balls of radius $1$ and $\ell$ balls of radius $0$. There are $2$-approximation
and $3$-approximation algorithms known for these problems respectively; the
former is best possible unless P=NP and the latter remains unimproved for 15
years.
  We first observe that no $O(1)$-approximation is to the optimal dilation is
possible unless P=NP, implying that the NUkC problem is more non-trivial than
the above two problems. Our main algorithmic result is an
$(O(1),O(1))$-bi-criteria approximation result: we give an $O(1)$-approximation
to the optimal dilation, however, we may open $\Theta(1)$ centers of each
radii. Our techniques also allow us to prove a simple (uni-criteria), optimal
$2$-approximation to the kCwO problem improving upon the long-standing
$3$-factor. Our main technical contribution is a connection between the NUkC
problem and the so-called firefighter problems on trees which have been studied
recently in the TCS community.
