<p>Though unrelated, <a href="https://cseweb.ucsd.edu/%7Edasgupta/291-geom/kmeans.pdf" rel="nofollow noreferrer">this</a> lecture note contains a potential function based neat proof of the <span class="math-container">$O(\log k)$</span>-approximation.</p>

CC BY-SA 4.0
2021-04-04T15:39:15.810Z
2021-04-04T15:39:15.810Z
Sudipta Roy
<p>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.</p>

<hr>

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

<p><span class="math-container">$OPT$</span> takes the center to be <span class="math-container">$r$</span>, at cost <span class="math-container">$\sum_{i=1}^{n-1} 1^\ell = n-1$</span>.  </p>

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

<hr>

<p>BTW, the published version of the manuscript appears to be here:</p>

<p><a href="https://dl.acm.org/doi/abs/10.5555/1283383.1283494" rel="noreferrer">https://dl.acm.org/doi/abs/10.5555/1283383.1283494</a></p>

CC BY-SA 4.0
2020-05-26T00:54:03.697Z
2020-05-26T00:54:03.697Z
Neal Young
<p>I was reading this popular paper <strong>"k-means++: The Advantages of Careful Seeding"</strong>. It appeared in <em>SODA 2007</em>. Since this technique is the most popular clustering technique, I am hoping that my question can be answered.</p>

<p>I found two versions of the paper (which I find contradictory):</p>

<ol>
<li><p><a href="http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf" rel="noreferrer">http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf</a></p></li>
<li><p><a href="https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf" rel="noreferrer">https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf</a></p></li>
</ol>

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

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

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

<p>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?</p>

<p>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.   </p>

<approximation-algorithms><randomized-algorithms><clustering><metric-spaces>
kmeans++ for arbitrary metric spaces and general potential function
Inuyasha Yagami
# kmeans++ for arbitrary metric spaces and general potential function

(Asked by: username_0 on 2020-05-25)

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.

**Tags:** approximation-algorithms, randomized-algorithms, clustering, metric-spaces


---

## 2 answers

### Answer by username_2 on 2020-05-26. Score: 6 | Accepted answer

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 by username_1 on 2021-04-04. Score: 1

Though unrelated, [this](https://cseweb.ucsd.edu/%7Edasgupta/291-geom/kmeans.pdf) lecture note contains a potential function based neat proof of the $O(\log k)$-approximation.


---

