kmeans++ for arbitrary metric spaces and general potential function
Here's an example that suggests that the stronger claim in the earlier version (Lemma 5.3) is false.  I've only given a cursory look at the papers, so please check this carefully to make sure I am understanding correctly, thanks.



Consider a cluster $X$ consisting of a rooted star: a root $r$ and $n-1$ nodes $v_1,v_2,\ldots, v_{n-1}$ such that $d(r, v_i) = 1$ for each $i$, and $d(v_i, v_j) = 2$ for each $i, j$ with $i\ne j$.

$OPT$ takes the center to be $r$, at cost $\sum_{i=1}^{n-1} 1^\ell = n-1$.  

But suppose the center $c$ is chosen at random. Then with probability $1-1/n$ the center is one of the $v_i$'s (not the root), and then the cost is $1+\sum_{j\ne i} 2^\ell \ge (n-1)2^\ell$.  So the expected cost is at least $(1-1/n) 2^\ell \,OPT$.



BTW, the published version of the manuscript appears to be here:

https://dl.acm.org/doi/abs/10.5555/1283383.1283494