Answers are grounded in this paper and cite their sources.
In Non-Uniform k-Center, we are given a metric space $(V,d)$ and L levels of balls with prescribed radii r₁ ≥ … ≥ rL and nonnegative integer budgets k₁,…,kL. The goal is to place at most k_ centers of each level ∈ [L] in V and minimize the dilation $λ$ such that the corresponding balls of radii λr₁,,λrL 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 βλₒₚₜ such that, for each ∈ [L], the number of centers of the first levels is at most $α$ times their total budget. For every fixed ε>0, we give a randomized (1+ε,8+ε)-approximation and a deterministic (Oε(1),2+ε)-approximation, both running in polynomial time. Even for classical k-Center, obtaining an $(O(1),2-δ)$-approximation is NP-hard for every fixed δ∈ (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+ε,2+ε)-bicriteria approximation, which would almost match the classical $2$-approximation for k-Center.
No takes yet. Share an insight, caveat, or question.
Blauth et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: