kmeans++ for arbitrary metric spaces and general potential function

Question

I was reading this popular paper "k-means++: The Advantages of Careful Seeding". It appeared in SODA 2007. Since this technique is the most popular clustering technique, I am hoping that my question can be answered.

I found two versions of the paper (which I find contradictory):

1. http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf

2. https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf

I have a problem with section 5 ("Generalization") of the paper. The section describes a generalization of the kmeans++ algorithm for an arbitrary metric space with a general potential function $ \Phi^{[\ell]} \equiv \sum_{x \in \mathcal{X}} min_{c \in \mathcal{C}} \| x-c\|^{\ell}$, where $||x-c||$ denotes the distance in any metric space, $\mathcal{X}$ is the data-set, and $\mathcal{C}$ is the center set of size $k$.

Consider Lemma 5.3, of the first version. It says that -"For a cluster $A$, if we choose a point $p$ uniformly at random, then the expected cost of the cluster(with $p$ as a center) is at most $4 \cdot OPT(A)$". Before stating this lemma, they explicitly say that this result is independent of the value of $\ell$.

However, a contradictory result is mentioned in lemma 5.1 of the second version, which says that "For a cluster $A$, if we choose a point $p$ uniformly at random, then the expected cost of the cluster(with $p$ as a center) is at most $2^{\ell} \cdot OPT(A)$"

So far, I agree with the second version of the paper. However, it is possible that the first version came later with corrections. If the first version result is also correct, how to prove this result?

Note: Both these versions are highly cited and appear at the top in the google search. So I doubt if they are incorrect. Also, none of the versions mention anything about the corrections made in the paper.

Answer 1

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

Answer 2

Though unrelated, this lecture note contains a potential function based neat proof of the $O(\log k)$-approximation.