betaFeedback

WorksComputer Science

Nearly Optimal Dilation for Non-Uniform k-Center with Constant-Factor Budget Violation

Abstract

In Non-Uniform kk-Center, we are given a metric space (V,d)(V,d) and LL levels of balls with prescribed radii r1≥…≥rLr_1 \ge \ldots \ge r_L and nonnegative integer budgets k1,…,kLk_1,\ldots,k_L. The goal is to place at most kℓk_\ell centers of each level ℓ∈[L]\ell \in [L] in VV and minimize the dilation λλ such that the corresponding balls of radii λr1,…,λrLλr_1,\dots,λr_L cover VV. 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 kk-Center covers VV with dilation βλoptβλ_{\text{opt}} such that, for each ℓ∈[L]\ell \in [L], the number of centers of the first ℓ\ell levels is at most αα times their total budget. For every fixed ε>0\varepsilon>0, we give a randomized (1+ε,8+ε)(1+\varepsilon,8+\varepsilon)-approximation and a deterministic (Oε(1),2+ε)(O_{\varepsilon}(1),2+\varepsilon)-approximation, both running in polynomial time. Even for classical kk-Center, obtaining an (O(1),2−δ)(O(1),2-δ)-approximation is NP-hard for every fixed δ∈(0,1]δ\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+ε,2+ε)(1+\varepsilon,2+\varepsilon)-bicriteria approximation, which would almost match the classical 22-approximation for kk-Center.

Paper details

vlnc:W_ak8e6knh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…