Skip to content
Preprint

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

Oct 2026 · 0 citations
Computer Science

TL;DR

The iterative rounding framework of Byrka, Guo, Hu, Li, Wan, and Wang is refined, which gives a $(2+\varepsilon)-approximation for $k$-median, and the Euclidean $k$-median bound relies on a geometric inequality proved via a nonnegativity certificate constructed from positive-semidefinite kernels.

Abstract

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.

View source

Similar papers

Sep 2026

Rounding the Ball LP for Fair Max-Min Diversification

Given $n$ points in a metric space, partitioned into groups, $X_1,\dots,X_m$, and integer quotas, $k_1,\dots,k_m$, summing to $k$, the Fair Max-Min Diversification problem asks for a set of $k$ points, exactly $k_i$ from each group $X_i$, maximizing the minimum pairwise distance. Addanki et al. (ICDT 2022) described a...

Julián Mestre, Lam Khai Trinh, Anthony Wirth · 0 citations
Preprint Oct 2026

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

A novel nuanced analysis of local search that allows us to isolate a subset of clients on which the authors lose essentially nothing compared to the optimal solution, while losing an approximation factor of $3$ on the rest of the clients.

Rares-Darius Buhai, Vincent Cohen-Addad, Henry L. Fleischmann et al. · 0 citations
Preprint Oct 2026

Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes

The weighted edit distance $\mathsf{ed}^w(X,Y)$ is the minimum cost of an alignment of strings $X$ and $Y$, where a weight function $w$ specifies the cost of each character insertion, deletion, and substitution. For strings of total length $N$, the textbook dynamic program takes $O(N^2)$ time, and no $O(N^{2-\delta})$-...

Egor Gorbachev · 2 citations
Preprint Oct 2026

Near-Optimal Oracle Bounds for Isotropic Rounding

We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower boun...

Yang P. Liu, Richard Peng, Alicia Stepin et al. · 2 citations
Preprint Oct 2026

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

We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+\epsilon)$-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an $O_\epsilon(1)$-approximation with $(1+\epsilon)$-violations via complex extended configuration linear program...

Han Dai, Shi Li · 0 citations
Sep 2026

Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection

The weighted $k$-matroid intersection problem asks for a maximum-weight set that is independent in each of $k$ matroids on a common ground set. The natural LP relaxation optimizes over the intersection of the $k$ matroid independent set polytopes. It is conjectured that this LP has integrality gap at most $k-1$. The co...

Yu Cong, Ya-Jie Zhao · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.