让下一篇重要论文，不再错过。

原文摘要

In Non-Uniform $k$-Center, we are given a metric space $(V,d)$ and $L$ levels of balls with prescribed radii $r_1 \ge \ldots \ge r_L$ and nonnegative integer budgets $k_1,\ldots,k_L$. The goal is to place at most $k_\ell$ centers of each level $\ell \in [L]$ in $V$ and minimize the dilation $λ$ such that the corresponding balls of radii $λr_1,\dots,λr_L$ cover $V$. While this problem admits no subexponential approximation factor unless P=NP, the picture changes drastically when additional centers are allowed. An $(α,β)$-bicriteria approximation to Smooth Non-Uniform $k$-Center covers $V$ with dilation $βλ_{\text{opt}}$ such that, for each $\ell \in [L]$, the number of centers of the first $\ell$ levels is at most $α$ times their total budget. For every fixed $\varepsilon>0$, we give a randomized $(1+\varepsilon,8+\varepsilon)$-approximation and a deterministic $(O_{\varepsilon}(1),2+\varepsilon)$-approximation, both running in polynomial time. Even for classical $k$-Center, obtaining an $(O(1),2-δ)$-approximation is NP-hard for every fixed $δ\in (0,1]$. Thus, our second result almost settles the optimal dilation when a constant-factor violation of the budget is allowed, unless P=NP. We combine a new primal-dual enumeration procedure with a simple bucketing argument that yields a new trade-off between the two approximation factors. It remains open whether there is a polynomial-time $(1+\varepsilon,2+\varepsilon)$-bicriteria approximation, which would almost match the classical $2$-approximation for $k$-Center.