cs.DSNov 9, 2026

Beyond the First Hit: Towards Tight Guarantees for kk-means++

Authors: Aravind Reddy

Organizations: Centre for Responsible AI, Wadhwani School of Data Science & AI, Indian Institute of Technology Madras

Abstract

Let RkR_k be the worst-case ratio between the expected cost of the kk seeds chosen by kk-means++ and the optimal kk-means cost. In their seminal paper introducing kk-means++, Arthur and Vassilvitskii (SODA 2007) showed that 2ln⁡k≤Rk≤8(ln⁡k+2)2\ln k\le R_k\le8(\ln k+2), and Makarychev, Reddy and Shan (NeurIPS 2020) improved the upper bound to 5(ln⁡k+2)5(\ln k+2). We prove Rk≤1163233+2.108 Hk−2R_k\le\frac{1163}{233}+2.108\,H_{k-2} for every k≥3k\ge3 by a computer-assisted argument, and Rk≤5+2.3139 Hk−2R_k\le5+2.3139\,H_{k-2} for every k≥2k\ge2 by a short analytic argument; here HjH_j is the jjth harmonic number. Since Hk−2≤1+ln⁡kH_{k-2}\le1+\ln k, this lowers the leading coefficient of ln⁡k\ln k from 55 to 2.1082.108. We also determine R2=5R_2=5 and R3=185/32R_3=185/32 exactly; both are suprema that are approached but not attained. On the lower side we prove Rk≥2(1+Hk−1)R_k\ge2(1+H_{k-1}) for every kk, and give a second family of lower bounds that is larger than this for 2≤k≤182\le k\le18. Previous analyses bound the expected cost of a cluster just after it is first sampled by a constant times its optimal cost, and then charge that cost for the rest of the run. We instead track how a cluster's cost evolves after its first hit: a cluster left with a large residual cost is likely to be sampled again before it accumulates much of the logarithmic charge, and each repeat repairs it.

Figures & tables

Explore similar work

Jul 28, 2026

Randomizing the Number of Centers in k-means++

The kk-means++ algorithm is a standard and widely used seeding method for kk-means clustering, but for a fixed number kk of centers its worst-case expected approximation ratio is Θ(log⁡k)Θ(\log k). We consider the same algorithm when an adversary first fixes the dataset and some KK; the number of centers kk is then chosen uniformly from {K,…,2K−1}\{K,\ldots,2K-1\}. We prove that kk-means++ is an O(1)O(1)-approximation with constant probability in this budget-smoothed setup.
Jul 9, 2026

An interpretable Good--Turing restart criterion for k-means++

The k-means++ algorithm is commonly restarted multiple times to avoid poor local optima, yet the number of restarts is almost always chosen arbitrarily and applied uniformly regardless of data set difficulty. This undermines any comparison relying on such a choice and wastes computation on easy data sets while potentially under-serving hard ones. We introduce GTRC, a restart criterion combining a Good-Turing estimate, a proven unconditional bound, and a confidence-based bound on the probability that a further restart would improve on the current result, stopping once this probability falls below a user-specified tolerance ε\varepsilon. Across 36 data sets, GTRC reached clustering quality competitive with well-chosen fixed restart counts, while the number of restarts used varied considerably and appropriately with data set difficulty, governed by an interpretable, data-dependent signal rather than a fixed rule. GTRC offers a principled and reportable alternative to fixing the number of kk-means++ restarts in advance. Software:https://github.com/RCdeAmorim/Good-Turing-Restart-Criterion.
Sep 7, 2026

A (3+ε)(3+ε)-Approximation for Fair kk-Means and a Matching Lower Bound

Fair clustering aims to prevent algorithmic bias against protected groups. We study Euclidean fair kk-means, in which the proportion of each protected group in every cluster lies between prescribed lower and upper bounds. Because these constraints violate the nearest-center assignment property, center selection is coupled with point assignment. We introduce the drift-regularized relaxation, a new convex relaxation solved by a modified Frank-Wolfe method with linear-programming iterations, whose optimality condition controls the cost of converting its solution into kk fair clusters. Combined with any ρρ-approximation algorithm for weighted kk-means, the relaxation yields an exactly fair fractional solution of cost at most 2ρ+1+ε2ρ+1+ε times the fractional optimum, improving the previous ratio 1+4ρ+ε1+4ρ+ε. In fixed dimension, this improves the best known ratio from 5+O(ε)5+O(ε) to 3+O(ε)3+O(ε). The fractional solution can be rounded to an integral one without changing the centers or increasing the cost, at a bounded additive violation of the fairness bounds. We also show that a (3−δ)(3-δ)-approximation is NP-hard for every fixed δ>0δ>0, even on the line with fractional assignments, so 33 is the exact approximation threshold for fractional fair kk-means in fixed dimension. The same guarantees hold for kk-sparse Wasserstein barycenters, a special case of fractional fair kk-means. More generally, they hold whenever every cluster must satisfy given homogeneous linear inequalities in the fractions of its points, such as a bound on the ratio between two groups or on the average of a numerical attribute in every cluster.