CS Paper Radar

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

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-13 10:52 UTC · v1
hot direction

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-10-12 ·Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann, Anupam Gupta, Antoni Jubés Monforte +4 more
similarity 0.71
Abstract · 44 + 8 pages, 8 figures

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.

0.50

Dynamic $k$-Median with Worst-Case Update Time and Recourse

cs.DS ·2026-11-12 ·Chenglin Fan
similarity 0.67
Abstract · 81 pages

We study fully dynamic metric $k$-median under unit-weight client insertions and deletions. After each update, the algorithm must maintain at most $k$ centers chosen from the current client locations. We give a randomized constant-factor approximation algorithm with $\widetilde O(k)$ worst-case update time and $O((1+\logΔ)^3)$ worst-case center recourse, where $Δ$ is the aspect ratio of the underlying metric space. The approximation guarantee holds simultaneously over any prescribed finite adaptive update sequence with high probability, while the update time and recourse bounds hold on every execution. We also obtain the same asymptotic guarantees for metric $k$-means.

0.25

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

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

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

Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

cs.DS cs.LGmath.OC ·2026-11-08 ·Vaneet Aggarwal
similarity 0.62
Abstract

Elements arrive one at a time, and after each arrival an algorithm holds a set of at most $k$ arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that $k$ arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of $k$ and of the number $n$ of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is $2-\sqrt{2}\approx0.5858$. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to $1-1/e\approx0.6321$, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds $1-1/e$, even when all elements are available at once. For every $\varepsilon>0$, a deterministic algorithm that sees the next $\lceil\varepsilon k/3\rceil$ arrivals keeps a set of value at least $1-1/e-\varepsilon$ times the optimum at every time, changes $O(\varepsilon^{-3})$ elements per arrival and makes $(n+1)^{O(\varepsilon^{-2})}$ evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with $O(\varepsilon^{-2})$ changes per arrival. A randomized algorithm with the same short lookahead makes $O(n^2k)$ evaluations, changes $O(\varepsilon^{-2})$ elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.

0.16

Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers

cs.DS ·2026-10-30 ·Zachary Friggstad, Pengfei Wu
similarity 0.61
Abstract

We study \textsc{Capacitated Facility Location}, a fundamental clustering problem, in the setting of uniform opening costs and non-uniform capacities. We give a polynomial-time $(3+ε)$-approximation for this problem. Our algorithm is a multiple-swap generalization of the local search algorithm by Dabas, Garg, and Gupta (2024), who obtained a $3.732$-approximation. The main technical contribution is the analysis of this natural multiple-swap local-search method: variants of this approach have been analyzed previously, but allowing larger swaps requires new grouping and counting arguments. We also show that a multiple-swap local search algorithm provides a $(3+ε)$-approximation for \textsc{Capacitated Facility Location with Outliers}, again in the same setting of uniform opening costs and non-uniform capacities. This is an improvement over the $6.372$-approximation, again by Dabas, Garg, and Gupta. Finally, we show that the factor $3$ is tight for our local-search framework, and that the same multiple-swap idea does not improve the known locality gap for the non-uniform opening-cost setting.

0.53

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