Noisy k-means++ is Not too Noisy

The celebrated $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) achieves an $O(\log k)$ expected approximation for the classical $k$-means problem using $D^2$-sampling, a technique now ubiquitous in clustering algorithm design. Bhattacharya et al. (ESA 2020) introduced $\epsilon$-noisy $k$-means++, where sampling probabilities may incur an adversarial multiplicative error of $(1\pm \epsilon )$, but obtained only an $O({\log }^{2}k)$ guarantee. Grunau et al. (ESA 2023) recovered the asymptotic $O(\log k)$ guarantee, but their analysis loses a constant factor of roughly $\mathrm{147,638}$ even as $\epsilon \to 0$, leaving open whether $k$-means++ is highly sensitive to even a small amount of noise. They asked whether a bound within $1+O(\epsilon )$ of the classical guarantee is possible. We resolve this affirmatively, proving an expected approximation guarantee of $8(\ln k+2){\left(\frac{1+\epsilon }{1-\epsilon }\right)}^4=(1+O(\epsilon ))8(\ln k+2)$. We complement the upper bound with two separations. First, a noisy version of the Arthur and Vassilvitskii lower-bound instance incurs a $1+\mathrm{\Omega }(\epsilon )$ loss over exact $k$-means++, so linear dependence on the noise is necessary. Second, pointwise multiplicative control is qualitatively essential: replacing it with per-round total variation closeness admits no finite approximation guarantee, even for $k=2$.