CS Paper Radar

$k$-Center under Weak and Strong Distance Oracles with an Application to Minimum Sum of Radii Clustering

Zachary Friggstad, Mahya Jamshidian, Ali Vakilian

cs.DS ·submitted 2026-10-30 23:24 UTC · v1
theory

Abstract

In the weak-strong distance oracle model of Bateni, Dharangutte, Jayaram and Wang (COLT 2024), a metric $(X,d)$ on $n$ points is accessed through two oracles: a cheap weak oracle that returns each queried distance correctly with probability $1-δ$ and permits arbitrary values on corrupted pairs, chosen by an adversary who knows the entire metric and all corrupted pairs, and an expensive strong oracle that reveals a point exactly. The goal is to cluster well while making as few strong queries as possible. Our main result is a $(6+\varepsilon)$-approximation for $k$-center using $O(k\log n\log(\varepsilon^{-1}\log n))$ strong point queries, for any fixed $\varepsilon>0$. This improves both the $(14+\varepsilon)$ approximation factor and the $O(k\log^2 n\log(\varepsilon^{-1}\log n))$ query bound of Bateni et al. It also improves the query complexity of the recent $(6+\varepsilon)$-approximation of Pradhan, Bhattacharya and Jaiswal (AISTATS 2026), in the variant of the model they study. Our algorithm outputs an explicitly known sketch of an otherwise unknown metric: a concrete metric on at most $k$ points that a downstream algorithm can compute with directly, with no further queries and no noise. As an application, we give a simple FPT algorithm for Minimum Sum of Radii (MSR) that returns a constant-factor solution using $2^{O(k\log k)}\cdot O(\log n\log\log n)$ strong queries. We complement the upper bound with an $Ω(k\log(n/k))$ lower bound for $k$-center with assignment that holds for row-local algorithms. These algorithms assign two unqueried points to the same center whenever their weak distances to the strong-queried points are exactly the same. Our algorithm and those of Bateni et al. and Pradhan et al. are all row-local, so our query bound is optimal for this class up to the $O(\log\log n)$ factor.

Comment
23 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Minimum Sum-of-Radii Clustering with Strong and Weak Oracles

cs.DS ·2026-11-16 ·Zachary Friggstad, Mahya Jamshidian, Ali Vakilian
theory similarity 0.87
Abstract · 42 pages

In the minimum sum of radii (MSR) problem, the input is a set of $n$ points in a metric space and a parameter $k$, and the goal is to cover the points by at most $k$ balls, each centered at an input point, while minimizing the sum of their radii. We study MSR in the weak-strong oracle model of Bateni, Dharangutte, Jayaram, and Wang (COLT'24), where the metric is unknown and is accessed through two oracles. The answers of the weak oracle are given to us for free: for every pair of points, we receive a distance value that, with probability $δ$, is arbitrarily corrupted. Exact distances are available only through costly strong queries, where a strong query on a point reveals its exact distances to all previously strongly queried points, and the goal is to minimize the number of strong queries. For every constant $δ< 1/2$, we give the first polynomial-time algorithm that makes $O(k \log n \log\log n)$ strong point queries and, with high probability, returns an $O(1)$-approximation for MSR; the previously best algorithm required running time and a number of strong queries exponential in $k$. This is within an $O(\log\log n)$ factor of a lower bound that we prove: any constant-factor approximation that succeeds with high probability on every instance must make $Ω(k \log n)$ strong queries in expectation on some instance. The same $Ω(k \log n)$ lower bound holds for $k$-center, where it matches the known upper bound up to an $O(\log\log n)$ factor. An optimal MSR cluster can be small both in size and in radius, so a uniform sample of strongly queried points may miss it entirely. Instead, our algorithm uses a packing LP over the balls certified so far to decide which points to query next. The analysis holds against an adversary who knows which pairs are corrupted.

0.22

Tight Bounds for k-Median++ and Improved Bounds for k-Means++

cs.DS ·2026-11-13 ·Haim Kaplan, David Naori
theory similarity 0.65
Abstract · 46 pages, 2 figures

The popular $k$-means++ algorithm, or $D^\ell$-sampling, is a fundamental primitive in both the theory and practice of clustering. In the bi-criteria setting, the algorithm samples $k+Δ$ centers ($Δ\ge0$), and its cost is compared with the optimum using $k$ centers. Despite extensive study over the past two decades, its exact approximation ratio and tight bi-criteria guarantees remain unknown. We give a unified analysis for every distance exponent $\ell>0$, every $k\ge1$, and every $Δ\ge0$. For metric $k$-median, our bounds are tight for all $k$ and $Δ$. Without extra centers, the exact approximation ratio is $2(1+H_{k-1})$ (also in Euclidean space), improving the previous upper bound by a factor of $2$ ($H_j$ denotes the $j$th harmonic number). This tight analysis reveals that even one extra center improves the approximation ratio by an additive $Θ(\log\log k)$, whereas previous bounds show no improvement. For every $\ell>0$, our analysis gives upper bounds with the same dependence on $k$ and $Δ$ as our tight bound for metric $k$-median, with leading constants depending only on $\ell$ and whether the metric is Euclidean. Beyond the improved dependence on $Δ$, our leading constants are smaller than those in previous analyses. In particular, for the widely used Euclidean $k$-means objective, our upper bound without extra centers is $(1+\varphi)(1+H_{k-1})$, where $\varphi\approx1.618$ is the golden ratio, improving upon the previous constant of $5$. With oversampling, a constant fraction of extra centers is known to provide a constant-factor approximation. For example, with $10\%$ extra centers, our guarantee is $5.7$, compared with the best previous guarantee of $25.9$.

0.23

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.64
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

Optimal Planar $k$ Nearest Neighbors Queries for Additively Weighted Euclidean Distances and Convex Metrics

cs.CG ·2026-10-12 ·Chih-Hung Liu
top venuetheory similarity 0.64
Abstract · 78 pages. A conference version will appear in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.

0.42

OverclusterDRG: a Deterministic, LP-Free Heuristic for Robust $k$-Center

cs.LG ·2026-11-13 ·Rudra Bhardwaj, Rajni Dabas, Neelima Gupta
similarity 0.64
Abstract · 11 pages, 7 figures, 8 tables

The $k$-center problem is a fundamental formulation for metric clustering. However, its min-max objective is highly sensitive to outliers, motivating the Robust $k$-Center (R$k$C) formulation which permits excluding up to $z$ points as outliers. Existing algorithms for R$k$C suffer from scalability issues: LP rounding relies on fractional relaxations that scale poorly, known combinatorial approximation algorithms are computationally expensive due to radius guessing, and scalable randomized heuristics require exponential trial multipliers to guarantee success. We present OverclusterDRG, a deterministic, LP-free heuristic for R$k$C. The algorithm leverages the theoretical insight of farthest-point oversampling -- adding exactly $z$ extra candidates to the center set to absorb outliers -- followed by a forward-greedy initialization and a $1$-swap local search. Evaluations across real-world datasets show that OverclusterDRG attains a mean approximation ratio of 1.147 against fractional LP lower bounds on the UCI Adult dataset, outperforming state-of-the-art baselines in both clustering quality and speed. By avoiding subset-guessing and exponential trial multipliers, it scales smoothly to $n=10^5$ points where LP solvers and theoretical algorithms become intractable.

0.20

Exact Sum-of-Radii Clustering under Any Constant Stability

cs.DS ·2026-11-02 ·Shyam Ravichandran, Lev Reyzin
similarity 0.63
Abstract · 27 pages

We establish a separation between the stability thresholds of Minimum Sum-of-Radii (MSR) clustering and two closely related objectives. Known hardness results show that, on general metrics, exact recovery for Minimum Sum-of-Diameters and symmetric $k$-center is hard for every fixed $1<γ<2$, unless NP=RP. We show that MSR admits deterministic polynomial-time exact recovery for every fixed $γ>1$, extending Gao and Reyzin's result for $γ\ge2$. All three results use the same Bilu--Linial stability model: the optimal partition remains uniquely optimal when each pairwise distance is multiplied by any factor in $[1,γ]$, without requiring the perturbed distances to satisfy the triangle inequality. The number of clusters is part of the input. For $1<γ<2$, our algorithm runs in $n^{O((γ-1)^{-5})}$ time. The main structural insight is that a cheap merge in one part of the instance would allow a profitable split elsewhere under a suitable perturbation, contradicting stability. The resulting exchange inequality controls local cluster density, which gives linear growth and hence bounded treewidth in local interaction graphs. We use random partitions to obtain these regions, solve them by dynamic programming, and then derandomize the construction. For rational input and fixed rational $γ>1$, recognizing stability in this model is coNP-complete. Verifying that a supplied partition remains uniquely optimal under all allowed perturbations is coNP-complete for both arbitrary symmetric and metric perturbations.

0.30

$L_1$ versus $L_2$ Clustering: When Does the Choice of Norm Matter?

cs.DS ·2026-11-04 ·Nick Gravin, Jianhao Jia
similarity 0.63
Abstract

We study how well approximation guarantees for clustering under one norm translate into guarantees under another. Specifically, we compare $k$-clustering in $\mathbb{R}^d$ under the $L_1$ and $L_2$ objectives, defined as the sums of Manhattan and Euclidean distances, respectively. In the worst case, the elementary relationship between these norms yields a $\sqrt{d}$ approximation bound, which is already tight for $k=2$. We therefore investigate whether stronger guarantees are possible in a natural average-case model, where the dataset is arbitrary but the coordinate system is chosen uniformly at random among all orthonormal bases. Our main result shows that, when $d=Ω(\log k)$, with high probability over the random rotation, any $β$-approximate $L_1$ clustering, with optimally chosen centers for its clusters, is also an $O(β)$-approximation under the $L_2$ objective. We also establish an expected approximation ratio of $O(β\min\{\sqrt{d},k^{2/d}\})$, yielding a dimension-independent bound of $O(β\sqrt{\log k/\log\log k})$. We obtain analogous guarantees in the reverse direction, from $L_2$ to $L_1$. We complement these results with lower bounds of $Ω(\min\{\sqrt{d},k^{1/d}\})$ in both directions, showing that our dimension-independent guarantees have asymptotically optimal dependence on $k$ for constant $β$. Our proofs overcome the dependence of the algorithm's output on the random rotation using geometric projection arguments and small Euclidean coresets. In particular, our results provide guarantees for existing clustering algorithms without requiring their redesign.

0.13

Streaming algorithms for computing coresets and $k$-median clustering in the Hamming space

cs.DS ·2026-08-25 ·Taha El Ghazi, Jonas Ellert, Chien-Chung Huang, Tatiana Starikovskaya
published similarity 0.63
Abstract · Accepted to WAOA 2026

Clustering is one of the most fundamental tools in data analysis, allowing large datasets to be summarized by a small number of representative points. Given a metric space $(\mathcal{X}, \mathbb{d})$ and a set $S$ of $n$ points in this space, the continuous $k$-median clustering problem asks to find a set $C$ of $k$ points that minimizes the objective function $\sum_{s\in S} \mathbb{d}(s,C)$. When $\mathcal{X} = Σ^\ell$ is the set of strings of length $\ell$ and $\mathbb{d}$ is the Hamming distance, the continuous $k$-median clustering problem is known to be W[1]-hard when parameterized by $k$. In this work, we present the first $(1+\varepsilon)$-approximation algorithm for this problem with FPT runtime $2^{\mathrm{poly}(\varepsilon^{-1},k)} \cdot n\ell \mathrm{polylog} \; n$. An additional feature of the algorithm is that it can be implemented in streaming, requiring only $\tilde{O}_\varepsilon(\ell k + k^2)$ space. As an auxiliary tool of independent interest, we show the first streaming algorithm for computing an $\varepsilon$-coreset for continuous $k$-median clustering under the Hamming

0.42