WorksComputer Science
Nearly Optimal Dilation for Non-Uniform k-Center with Constant-Factor Budget Violation
Abstract
In Non-Uniform -Center, we are given a metric space and levels of balls with prescribed radii and nonnegative integer budgets . The goal is to place at most centers of each level in and minimize the dilation such that the corresponding balls of radii cover . 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 -Center covers with dilation such that, for each , the number of centers of the first levels is at most times their total budget. For every fixed , we give a randomized -approximation and a deterministic -approximation, both running in polynomial time. Even for classical -Center, obtaining an -approximation is NP-hard for every fixed . 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 -bicriteria approximation, which would almost match the classical -approximation for -Center.