Improved coverage solutions with flexible center limits in distance problems

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

Data Structures and Algorithms

Summary

Some problems involve placing limited 'centers' on a map to cover all locations within certain distances. The authors study a complex version where centers can have different sizes and budgets. They show that by allowing a small, fixed increase in the number of centers, they can almost match the best possible coverage quality. Their methods work efficiently and clarify what can be achieved with slight relaxations in the rules.

What this means in practice

  • For network planners: Design wireless or sensor networks allowing small expansion in resource usage to nearly optimize coverage areas.
  • For logistics coordinators: Allocate facilities with flexible capacity limits to cover delivery points efficiently while relaxing strict constraints.

Authors

Jannis Blauth, Siri Prüßner

Abstract

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.