CS Paper Radar

A Better-than-$2$ Approximation for $k$-Median Part II: Stable Instances

Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann, Anupam Gupta, Antoni Jubés Monforte, Madhusudhan Reddy Pittu, Miltiadis Stouras, Ola Svensson, Lukas Vogl

cs.DS ·submitted 2026-10-12 17:44 UTC · v1

Abstract

We consider the $k$-median problem on general metric spaces, subject to the condition that the instances are $β$-stable (i.e., the optimal solution using $k-1$ centers has a cost at least $(1+β)$ times that of the optimal solution with $k$ centers). We give a $(1.89+ε)$-approximation algorithm for such instances running in time $\exp(1/(β\times \mathrm{poly}(ε)))\cdot \mathrm{poly}_ε(n)$. In particular, for $β=\mathrm{poly}(ε)/\log n$ and $ε$ a tiny constant, this is a polynomial-time algorithm. This improves on previous work showing a $(2 + ε)$-approximation algorithm with similar running time [CGL+25]. Combined with the pseudo-approximation algorithm in our companion work, this results in a better-than-$2$ approximation algorithm for general $k$-median instances. Our main technical contribution is a novel nuanced analysis of local search that allows us to isolate a subset of clients on which we lose essentially nothing compared to the optimal solution, while losing an approximation factor of $3$ on the rest of the clients. We complement this with an algorithm based on sampling and partial enumeration, achieving a better-than-$2$ approximation on the rest of the clients. Trading off these two algorithms yields our final approximation.

Comment
44 + 8 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering

cs.DS cs.CC ·2026-10-10 ·Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou
similarity 0.73
Abstract

Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother clustering criteria in the past three decades. In this paper we give an efficient approximation scheme for this problem that runs in sublinear time for mildly increasing $k$, and thus is fixed parameter tractable with respect to the parameter $k$. We complement this result by showing that similar algorithms are unlikely to exist for the closely related problems $k$-median and balanced $k$-median, assuming popular fine-grained complexity conjectures. Specifically, we show that no sublinear time algorithm with small approximation factors can exist even for $2$-median and balanced $2$-median. It was previously known that no efficient PTAS can exist for $k$-median and our results show a strong and perhaps surprising separation between the $k$-minsum clustering problem and $k$-median even in the sublinear regime. Our upper bounds improve qualitatively upon decades old results. Our lower bounds establish the first use of the Distributed PCP framework to clustering problems.

0.14

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

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

cs.DS ·2026-11-13 ·Haim Kaplan, David Naori
theory similarity 0.72
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

A Better-than-2 Approximation for k-Median Part I: The Power of General Bids

cs.DS ·2026-10-13 ·Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann, Anupam Gupta, Antoni Jubés Monforte +4 more
hot direction similarity 0.71
Abstract

The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus the engine behind the best $k$-median guarantees, for over two decades. Its $2$-LMP guarantee was only recently broken by a small amount ($(2-η)$-LMP where $η\approx 2.25 \cdot 10^{-7}$) through local-search post-processing. That analysis relies on the structure of worst-case instances, and it appears difficult to obtain substantial further improvements along those lines. We take a different approach and change the algorithm itself: we introduce general bidding functions, replacing the classical linear bid with a richer family of rules and prove a polynomial-time $1.95$-LMP approximation, a large improvement over the long-standing factor of~$2$. We further show that these generalized bidding rules can be made smooth (log-adaptive), building on the recent framework developed for the classical Greedy algorithm by Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson. This yields a polynomial-time $1.95$-approximation that opens $k+O_\varepsilon(\log n)$ centers. Combined with a $(1.89+\varepsilon)$-approximation algorithm for stable instances in our companion work \cite{stableinstances}, we achieve a better-than-2 approximation for the $k$-median problem in polynomial-time.

0.48

A Configuration-LP Framework for Connected $k$-Median Clustering

cs.DS ·2026-08-28 ·Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian
hot direction similarity 0.68
Abstract · This paper has been accepted in Approx 2026

We study the \emph{connected $k$-median} clustering problem, a clustering problem that augments the classical $k$-median objective with connectivity constraints. We focus on the \emph{overlapping} variant of the problem, where clusters are allowed to share vertices. In addition to a metric space $(V,d)$, the input contains a connected graph $G$ on the same vertex set $V$ of size $n$. The goal is to select at most $k$ centers $C$ and assign vertices to them so as to minimize the $k$-median cost (i.e., $\sum_{v\in V} d(v,C)$), subject to the constraint that each cluster induces a connected subgraph of $G$. Since the metric space and the connectivity graph are independent, the problem is significantly more challenging than standard clustering. Eube et al.~\cite{eube2025esa} showed that even the assignment version is $Ω(\log n)$-hard to approximate and gave approximation algorithms with guarantees depending polynomially on $k$. We develop a configuration-LP-based framework that combines covering LP techniques with a rooted minimum-density oracle. For the assignment version, we obtain an $O(\log^2 n)$-approximation. For the general version, we develop a bicriteria framework that opens $O(k\log n)$ centers while achieving an $O(\log^2 n)$-approximation in cost. %Our results provide a different LP-based approach for handling connectivity constraints in clustering problems and demonstrate that configuration LPs, covering LPs, and rooted density oracles can be combined effectively to obtain approximation guarantees for clustering objectives under graph-theoretic constraints.

0.30

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

Simpler Algorithms for Capacitated $k$-Median with $(1 + ε)$-Violations Using New Inequalities

cs.DS ·2026-10-16 ·Han Dai, Shi Li
published similarity 0.65
Abstract · Accepted at SOSA 2027

We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+ε)$-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an $O_ε(1)$-approximation with $(1+ε)$-violations via complex extended configuration linear programming formulations with the round-or-cut framework. We propose a simpler, unified round-or-cut framework that handles both cardinality and capacity violation settings. Our main technical contribution is a mechanism that directly utilizes the costs of local instances to generate valid inequalities. Specifically, we partition the metric space into local pieces of size $O(1/ε)$ as in previous work, and construct instances of capacitated clustering with penalties, which allow client demands to be unserved at a penalty cost. Solving these local instances yields lower bounds on the original LP cost, yielding valid LP constraints. In contrast, previous approaches rely on complex extended configuration LPs over connection variables $x_{ij}$'s and opening variables $y_i$'s. As a secondary contribution, our approach achieves an improved running time of $\text{poly}(n, 1/ε)$, bypassing the exponential dependence on $1/ε$ required to solve the previous extended configuration LPs. Instead of solving the local instances optimally in time exponential in $1/ε$, we obtain $O(1/ε)$-approximate solutions in $\text{poly}(n, 1/ε)$ time. Finally, for the cardinality-violation setting, our algorithm opens a set of at most $(1+ε)k$ $\textit{distinct}$ facilities, and thus gives a bicriteria approximation in the $\textit{hard-capacitated}$ setting. In contrast, the algorithm of [Li16] may open the same facility multiple times.

0.33

Iterative Randomized Rounding for $k$-Median in General and Euclidean Metrics

cs.DS ·2026-10-22 ·Jarosław Byrka, Yuhao Guo, Yang S. Hu, Shi Li, Yongho Shin +3 more
similarity 0.65
Abstract · 76 pages, 1 figure. The abstract was abridged to meet the arXiv requirement

We refine the iterative rounding framework of Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which gives a $(2+\varepsilon)$-approximation for $k$-median. Our algorithm opens $k+O(1)$ facilities with expected connection cost at most $1.9999$ times the standard LP value. Despite the small numerical gain, this shows that the LP integrality gap is below $2$ with a constant additive facility allowance, partially answering Li and Svensson's open question [SICOMP'16]. Their reduction yields a $1.9999$-approximation opening at most $k$ facilities. Our preprocessing makes the LP solution $\mathrm{poly}(\varepsilon)$-integral with a $(1+\varepsilon)$ loss in each client's expected connection cost and $O(1)$ extra facilities, without special treatment of clients with concentrated fractional facilities. We replace batch processing with single-facility openings and combine a tighter analysis for clients with unequal distances to their facilities with a complementary algorithm for nearly uniform distances. In Euclidean metrics, we obtain a $1.71955$-approximation for $k$-median and a $1.4561$-approximation for uncapacitated facility location (UFL). For every $p\ge2$ and sufficiently small $\varepsilon>0$, we obtain a $((3^p+2)/3+\varepsilon)$-approximation for $k$-clustering with $p$-th power distance costs. For $p=2$, our $(11/3+\varepsilon)$-approximation for $k$-means improves the $(3+\ln2+\varepsilon)$ bound of Anand, Charikar, Cohen-Addad, Gao, Grandoni, Lee, Sharma, and van Wijland [SODA'27]. The Euclidean $k$-median, $k$-means, and UFL ratios are below the respective general-metric hardness bounds $1+2/e$, $1+8/e$ [STOC'02], and $1.463$ [J. Algorithms'99]. The Euclidean $k$-median bound relies on a geometric inequality proved via a nonnegativity certificate constructed from positive-semidefinite kernels.

0.14