Inapproximability of $(\alpha, \beta)$ bi-criteria approximation
This problem generalizes dominating set: given an unweighted graph, there exists a set of k centers such that all other vertices are at distance 1 from them if and only if there exists a dominating set of size k.

Dominating set is hard to approximate with a ratio better than $\ln n$. In the above observation the optimal value for the k-center problem is either 1 or at least 2. Let $A$ be a $(c,2-\epsilon)$ bi-criteria approximation for $k$-center for some $c &lt; \ln n$. If a dominating set of size $k$ exists, then the corresponding $k$-center problem would have optimum cost of 1, and $A$ would return a solution of cost at most $2-\epsilon$ using at most $k \ln n$ centers. Thus, $A$ can be used to find a $\ln n$ approximation for dominating set, which is known to be not possible. Therefore, I think that no $(c,2-\epsilon)$ bi-criteria approximation can exist for $c&lt;\ln n$.