CS Paper Radar

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

Jannis Blauth, Siri Prüßner

cs.DS ·submitted 2026-11-12 17:00 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Coreset Bounds for $(k,z)$-Clustering in Euclidean and Doubling Metrics

cs.DS cs.CG ·2026-10-25 ·Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu
theory similarity 0.62
Abstract

We determine the optimal worst-case size of strong coresets for $(k,z)$-clustering in Euclidean spaces and doubling metrics, up to polylogarithmic factors. In Euclidean space, previous lower bounds matched the best upper bounds only for $\varepsilon\gtrsim k^{-1/(z+2)}$. We close the gap for arbitrarily small $\varepsilon$, establishing the optimal size $\widetildeΘ(\min\{k^{(2z+2)/(z+2)}\varepsilon^{-2},\,k\varepsilon^{-z-2}\})$ for every fixed $z\ge1$, all $k\ge1$, and $0<\varepsilon<1$. Our lower bound replaces each offset in a previous hard instance by a group of distinct offsets. A fixed family of $k$-center queries and four-wise independent signs force a large relative cost error for every sufficiently small subset with arbitrary nonnegative weights. For doubling metrics of dimension $D$, we resolve the previously unmatched bounds for $z>2$. We prove an upper bound of $\widetilde O(k^{2-2/z}D\varepsilon^{-2})$ and a lower bound that, together with known upper bounds, establishes the optimal size $\widetildeΘ(kD\min\{k^{1-2/z}\varepsilon^{-2},\,\varepsilon^{-z}\})$ for fixed $z>2$, $0<\varepsilon\le\varepsilon_z$, and $D\ge C_z\log(2/\varepsilon)$, where $C_z>0$ and $\varepsilon_z\in(0,1)$ depend only on $z$. The lower bound exploits the ability to encode $Θ(D)$ independent signs per center without diluting relative cost discrepancy. For the upper bound, we use independent, unbiased two-point summaries that exactly preserve cluster mass and anchor cost, combined with iterative size reduction.

0.21

Parameterized Complexity and Geometric Approximation of Riesz Energy Subset Selection

cs.CG cs.CCcs.DS ·2026-11-10 ·Michael Emmerich, Soumen Atta
code/data similarity 0.62
Abstract · 35 pages, 6 figures. Code, data, and instructions for reproducing the experiments: https://github.com/emmerichmtm/PCGA-Riesz

We choose $k$ of $n$ sites to minimize Riesz $s$-energy, in which a pair at distance $t$ contributes $t^{-s}$. For $s=2$, exact selection is polynomial on a line but NP-hard in the plane. Adapting the proxy lemma of Ceccarello et al. gives an efficient parameterized approximation scheme (EPAS) for fixed Euclidean dimension and fixed $s>0$. To sharpen the bound, we start with a geometric packing. Farthest-first traversal gives $2k$ centers separated by at least the last insertion distance $r$. If one site of an optimum is removed, each of the $k-1$ remaining sites excludes at most one center closer than $r/2$, leaving at least $k+1$ centers free. The new step is a discrete exchange bound: the removed site's interaction energy is at most the average it would contribute at those free centers. In the plane at $s=2$, this reduces the representative bound from $O(k^2\log(2k)/\varepsilon^2)$ for a packing estimate of total energy to $O(k\log(2k)/\varepsilon^2)$, independently of $n$. Rational planar examples show that the resulting separation scale $r/\sqrt{\log(2k)}$ is sharp. A $(1+\varepsilon)$ approximation on rational planar sites takes $O(nk+n\log n)+(C\log(2k)/\varepsilon^2)^k$ operations of polynomial bit cost. The observed number $M$ of representatives determines the search size $\binom{M}{k}$. With one million sites, $k=5$ and $\varepsilon=1/2$, the exchange grid left 252 subsets on clustered inputs and about $9.3\times10^{26}$ on uniform inputs. The method extends to metrics of bounded doubling dimension and to compact domains with effective geometric routines, including filled simple polygons. At $s=2$, exact decision on metrics with nonzero distances in $\{1,2\}$ is W[1]-complete in $k$. A gap that shrinks with $k$ rules out a deterministic EPAS on unrestricted metrics unless FPT = W[1].

0.49

Constant-Factor Approximation for Capacitated Clustering in Low Dimension with $(1+ε)k$ Centers

cs.CG cs.DS ·2026-10-29 ·Kangke Cheng, Guanlin Mo, Hu Ding
similarity 0.62
Abstract

In many applications of $k$-median and $k$-means, including load balancing and redistricting, each center can serve only a bounded number of clients. This leads to capacitated clustering, in which a client may be forced to use a distant center because all nearby ones are full. This loss of locality defeats the techniques behind approximation schemes, and no constant-factor approximation is known in general metrics even for capacitated $k$-median. A long line of work therefore opens $K=k+\lfloorεk\rfloor$ centers for a fixed $ε\in(0,1]$, while respecting the capacities exactly. We give a deterministic polynomial-time algorithm for uniform soft capacities in low dimension, that is, when the clients or the center locations have bounded doubling dimension. With $K$ centers, its ratio is $3-2ε$ for $k$-median and $9-8ε$ for $k$-means, or $5-4ε$ in $\mathbb{R}^d$. Apart from $k$-median in the plane, these are the first polynomial-time ratios bounded by a constant independent of $ε$; previously, the best ratio was $O(ε^{-2}\log(1/ε))$, even for $k$-median. We also obtain ratios that stay bounded as $ε\to0$ for non-uniform and hard capacities in low dimension, and ratios polylogarithmic in $1/ε$ in general metrics. Our approach starts from a simple structural observation: a near-optimal uncapacitated solution can be split into fewer than $2k$ capacity-respecting blocks, so $2k$ centers already suffice, one per block. Our main tool, the rescue lemma, shows that once every block that sends clients to a center of the optimal solution is rescued (given a private center), that center can be closed, so each extra center effectively rescues about two blocks. This lets $\lfloorεk\rfloor$ extra centers rescue nearly an $ε$-fraction of the blocks, yielding the linear dependence on $ε$ in our ratios.

0.16

On the weighted hard-core model and Rado's covering problem for congruent Euclidean balls

cs.DM math.MGmath.CAmath.CO+1 ·2026-08-10 ·Chengfei Xie, Gennian Ge
theory similarity 0.60
Abstract · 17 pages; any comments are welcome

Let $K$ be a symmetric convex body in $\mathbb{R}^d$ and let $f(K)$ denote the largest constant $c$ such that every finite collection of translates of $K$ contains a pairwise disjoint subcollection whose total volume is at least $c$ times the volume of the union of the original collection. The classical Vitali covering lemma gives $f(K)\geq3^{-d}$. In this paper, we establish two improvements. First, by a purely combinatorial argument, we prove that $$ f(K)\geq \frac{2}{3^d + 2^d} $$ for every symmetric convex body $K$. This improves the Vitali bound by a factor tending to $2$ as $d$ tends to infinity. Second, using a weighted hard-core model together with a weighted geometric estimate for intersections of Euclidean balls, we show that, for all sufficiently large $d$, $$ f(B^d)\geq \left( \log\frac{3}{1+\sqrt3} -O\left(\frac{\log d}{d}\right) \right)d\,3^{-d}, $$ where $B^d$ is the unit Euclidean ball in $\mathbb{R}^d$. Thus, the classical lower bound is improved by a factor of order $d$.

0.38

Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means

cs.CG cs.CCcs.DSstat.ML ·2026-11-11 ·Karthik C. S., Dor Minzer
theory similarity 0.60
Abstract

In the Euclidean $k$-means problem, we are given a set of $n$ points in $\mathbb{R}^d$, and the goal is to find $k$ representative points in space so as to minimize the sum of the squared distances from each point to its closest representative. Algorithmically, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] obtain a $(1+\varepsilon)$-approximation for high-dimensional Euclidean $k$-means in time $2^{(k/\varepsilon)^{O(1)}} \cdot dn^{O(1)}$, which was subsequently improved to $2^{\tilde{O}(k/\varepsilon)} + O(ndk)$ by Feldman, Monemizadeh, and Sohler [SoCG'07]. On the lower-bound side, a recent work of Cohen-Addad, Karthik, Saulpic, and Schwiegelshohn [SoCG'26] proposed the Exponential Time for Expanders Hypothesis (XXH), which asserts exponential-time hardness for $(1+\varepsilon)$-approximating Vertex Cover on vertex expanders, and used it to prove nearly matching running time lower bound whenever $k=\tildeω(1/\varepsilon)$. We observe that XXH does not hold in the parameter regime needed for the above result, and show how to repair their reduction under a more standard assumption. More precisely, we show that assuming the Almost Exponential Time Hypothesis for 3-SAT (Almost ETH), for every constant $β\in(0,1)$, Euclidean $k$-means in $\mathbb{R}^d$ has no $(1+\varepsilon)$-approximation algorithm running in time $2^{(k/\varepsilon)^{1-β}}\text{poly}(n,d)$, whenever $k=\tildeω(1/\varepsilon)$. By modifying the construction, we also obtain a similar result for approximating the Euclidean $k$-median problem.

0.12

Subexponential Parameterized Approximation for Group-Fair Euclidean $k$-Center

cs.DS ·2026-10-14 ·Rudranarayan Kar, Diya Roy, Abhishek Sahu
similarity 0.58
Abstract

Clustering is a basic tool for grouping data into meaningful classes, but in many applications the resulting clusters must also respect the fairness conditions among different groups. We study this direction for the group-fair Euclidean $k$-center problem in fixed dimension, where the input points are partitioned into disjoint color classes, and every cluster must satisfy given lower and upper bounds on the fraction of each color. We give a separator-based recursive approximation algorithm for the continuous-center setting. The main idea is to first reduce the continuous search space to a finite candidate center set and then use the geometric sphere separators to break the instance into smaller subproblems. Our algorithm gives a bicriteria approximation: the clustering radius is within a factor of $(1+ε)$ of the optimum exactly fair solution, while the fairness bounds are relaxed only by a multiplicative factor. For fixed dimension, number of colors, and approximation parameters, the running time is polynomial in input size and subexponential in $k$. A recent IJCAI-ECAI2026 result gives a $(1+ε)$-approximation for group-fair $k$-center in bounded doubling metrics with running time $(k/ε)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. In the fixed-dimensional Euclidean setting considered here, we improve the dependence on $k$ to subexponential, while allowing continuous centers. The fairness guarantees of the two results are different: the previous work allows an additive fairness violation, whereas our algorithm uses a controlled multiplicative relaxation.

0.07

Layering and reverse extension for weighted $k$-path vertex cover

cs.DS cs.DM ·2026-10-29 ·Jiajing Wu, An Zhang, Shiming Li, Guohui Lin
similarity 0.57
Abstract · 13 pages; submitted for publication

We study the weighted $k$-path vertex cover problem for any fixed integer $k \ge 2$, in which a vertex non-negatively weighted simple graph $G = (V, E)$ is given and one wants to find a minimum-weight vertex subset $C \subseteq V$ such that every simple path on $k$ vertices in $G$ contains at least one vertex of $C$. The problem generalizes the classic weighted vertex cover problem, that is, $k = 2$, and it admits a $k$-approximation algorithm of Hochbaum~[SIAM J. Comput., 1982] and a $(k - \frac 12)$-approximation algorithm of Brüstle et al.~[IWOCA 2021]. In this paper, we carefully design local weight functions in the Layering and Reverse Extension local ratio framework of Bar-Yehuda et al.~[ACM Comput. Surv., 2004], leading to an approximation algorithm of ratio $\frac {3k-1}4$ for odd $k \ge 3$ and of ratio $\frac {3k}4$ for even $k \ge 4$. When $k = 3$ and $k = 4$, these ratios are $2$ and $3$, respectively, matching the state-of-the-art approximation ratios for the corresponding special cases.

0.15

Curves of constant width and Lebesgue's covering problem

cs.CG math.MG ·2026-08-31 ·Ujjwal Mishra
theory similarity 0.57
Abstract

A universal cover is a convex set in the plane that contains a congruent copy of every planar set of diameter one. Lebesgue asked in 1914 for one of least area, and the value is not known. We prove that every convex universal cover has area at least 0.8344, improving on 0.832, published in 2005, and 0.833, in a 2026 preprint, both of which come from a disc together with an equilateral triangle and a regular pentagon. Our test sets are instead curves of constant width: the disc, the Reuleaux triangle and the Reuleaux pentagon. Each contains the regular polygon it is built on, so the family is strictly larger at the same number of bodies and the same number of placement parameters, and we show that the classical configuration admits an arrangement whose hull has area below 0.8336, so no bound drawn from those three sets by this argument reaches ours. Curves of constant width were proposed for this role, and explored numerically, by Gibbs in 2014; what is added here is a proof. It consists of an analytic reduction followed by one finite computation. The reduction bounds the hull area from below over an entire box of placements at once, by eroding each Reuleaux polygon to a fixed set contained in every placement that box allows. The computation is an exhaustive subdivision of the resulting five-dimensional space, recorded as a certificate of 486,799,600 nodes and checked by a verifier independent of the search, with a rigorous bound on its floating point error some thousands of times smaller than the margin the verification attains.

0.16