<p>Lets recall the definition of <span class="math-container">$k$</span>-means clustering for euclidean spaces.</p>
<p>Let <span class="math-container">$X$</span> be a set of <span class="math-container">$n$</span> points in <span class="math-container">$R^d$</span> and <span class="math-container">$k$</span> a given natural number. Let <span class="math-container">$C$</span> any <span class="math-container">$k$</span> clustering of <span class="math-container">$X$</span>. Define the cost of <span class="math-container">$C$</span></p>
<p><span class="math-container">$\phi(C) = \sum_{i=1}^k \sum_{x \in C_i} \|x-\mu_i\|_2^2$</span></p>
<p>where <span class="math-container">$\mu_i = mean(C_i)$</span>.</p>
<p>Then the goal is to find a <span class="math-container">$C^*$</span> minimizing <span class="math-container">$\phi$</span>. This problem is NP-Hard, even for <span class="math-container">$k=2$</span>.</p>
<p>However there several approximation algorithms for it, e.g. k-means++; but also constant factor approximation algorithms and PTAS.</p>
<p>What I'm looking for is a reference for exact algorithms (i.e., algorithms finding an optimal clustering) which are not polynomial but better than exhastive search. The only reference I'm aware of is (<a href="https://dl.acm.org/doi/10.1145/177424.178042" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/177424.178042</a>), which is quite old.</p>

CC BY-SA 4.0
2020-09-15T21:50:28.337Z
Thanks, I've elaborated more on it.
Andrea
CC BY-SA 4.0
2020-09-16T06:22:08.270Z
@D.W. Technically, k-means is a problem, as defined in the question. It is just that "Lloyd's heuristic" is popularly known as the k-means algorithm.
Inuyasha Yagami
CC BY-SA 4.0
2020-09-16T09:12:37.727Z
I don't know of recent work on absolute worst-case instances, but k-means on smoothed instances can be solved in polynomial time, see [AMR09](https://arxiv.org/pdf/0904.1113.pdf).
Yonatan N
CC BY-SA 4.0
2022-01-18T01:49:54.087Z
@InuyashaYagami Are the constant factor approximaion algorithm for this problem?
ErroR
CC BY-SA 4.0
2022-01-18T06:19:48.337Z
@Jut The current best approximation guarantee is $6.129$. See [here](https://arxiv.org/abs/2107.07358). The first known constant approximation was around 2 decades earlier.
Inuyasha Yagami
CC BY-SA 4.0
2022-01-19T02:51:17.900Z
@InuyashaYagami Thank you. Are we have any constant factor approximation algorithm for k-Means in plane?
ErroR
CC BY-SA 4.0
2022-01-19T11:40:44.900Z
@Jut This is not an appropriate place to ask this question. It would be spamming the comment section. You may want to take this discussion to chat; I will answer your questions there.
Inuyasha Yagami
CC BY-SA 4.0
2022-01-20T04:37:47.250Z
@InuyashaYagami Unfortunately, I can't take this discussion to chat, because I'm temporarily suspended from Stackexchage.
ErroR
CC BY-SA 4.0
2022-01-21T21:05:22.830Z
@Jut PTAS is known when $d$ is fixed. See [here](https://arxiv.org/abs/1603.08976).
Inuyasha Yagami
<reference-request><optimization><clustering>
Exact algorithms for $k$-means
Andrea
# Exact algorithms for $k$-means

(Asked by: username_0 on 2020-09-14)

Lets recall the definition of $k$-means clustering for euclidean spaces.

Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $C$

$\phi(C) = \sum\_{i=1}^k \sum\_{x \in C\_i} \|x-\mu\_i\|\_2^2$

where $\mu\_i = mean(C\_i)$.

Then the goal is to find a $C^\*$ minimizing $\phi$. This problem is NP-Hard, even for $k=2$.

However there several approximation algorithms for it, e.g. k-means++; but also constant factor approximation algorithms and PTAS.

What I'm looking for is a reference for exact algorithms (i.e., algorithms finding an optimal clustering) which are not polynomial but better than exhastive search. The only reference I'm aware of is (<https://dl.acm.org/doi/10.1145/177424.178042>), which is quite old.

**Tags:** reference-request, optimization, clustering

> **Comments:**
> **username_0**: Thanks, I've elaborated more on it.  
> **username_1**: @D.W. Technically, k-means is a problem, as defined in the question. It is just that "Lloyd's heuristic" is popularly known as the k-means algorithm.  
> **username_2**: I don't know of recent work on absolute worst-case instances, but k-means on smoothed instances can be solved in polynomial time, see [AMR09](https://arxiv.org/pdf/0904.1113.pdf).  
> **username_3**: @InuyashaYagami Are the constant factor approximaion algorithm for this problem?  
> **username_1**: @Jut The current best approximation guarantee is $6.129$. See [here](https://arxiv.org/abs/2107.07358). The first known constant approximation was around 2 decades earlier.  
> **username_3**: @InuyashaYagami Thank you. Are we have any constant factor approximation algorithm for k-Means in plane?  
> **username_1**: @Jut This is not an appropriate place to ask this question. It would be spamming the comment section. You may want to take this discussion to chat; I will answer your questions there.  
> **username_3**: @InuyashaYagami Unfortunately, I can't take this discussion to chat, because I'm temporarily suspended from Stackexchage.  
> **username_1**: @Jut PTAS is known when $d$ is fixed. See [here](https://arxiv.org/abs/1603.08976).  

---

## 0 answers

