1
$\begingroup$

coming from the computing science side rather than from the data analysis one, I studied the k-means clustering problem for a short time and noticed that the NP-hardness of the problem for $k=2$ seems to be separately proved in various places (publications as well as some online PDFs). For instance, the article NP-hardness of Euclidean sum-of-squares clustering (link found on Wikipedia) proves the result for $k=2$ only.

What I don't understand well is that proving such a result seems to lead to an easy one-sentence generalization (see below) to any value of $k$. Knowing very little about the k-means problem, I am pretty sure I am missing something but why not add the following claim to all these articles?

Having proved the NP-hardness of the k-means problem for $k=2$, we notice that any instance of the problem for some value of $k$ can be reduced to an instance of the same problem for the case $k+1$ (by adding one more point to the dataset far enough from all existing points), we easily prove the NP-hardness of the problem for any value of $k$.

For instance, say I want to solve the problem for some $k$ and $n$ points in $[0,1]$. I know the sum of the square is smaller than $n$. I now add the new point $1+\sqrt{2n}+\epsilon$ to the dataset, building an instance of the clustering problem for $k+1$. The solution must put this new point alone in a separate cluster (thus not changing the previous sum of squares); because in any other case the new sum of squares would be greater than $n$. Thus solving this new problem for $k+1$ clusters immediately solves the initial instance of the problem. Of course, the very same idea can be used for the plane or any euclidean space.

$\endgroup$

1 Answer 1

1
$\begingroup$

I think this is a matter of convention in how people communicate the results. It would be one thing to say "The k-means problem is NP-hard [when k is allowed to be any number up to $n$, the number of data points]". People might still then hope that there was, say, a $O(n^k)$ algorithm. Subsequently someone may prove that there is some finite $k$ such that the k-means problem is NP-hard, but that this required $k \ge 10^5$. Then people would surely try to modify the approach to show hardness for smaller and smaller values of $k$, until the end of the race: that for all $k \ge k_0$ it is NP-hard, and for all $k < k_0$ it's in $P$.

Each of those improvements, where they reduce $k_0$, would often write their result as "We show that k-means is NP-hard even when $k=2$". They certainly could write $\ge$, but that feels like a given, and to them their theorem might "really" be saying, "We've shown $k_0 \le 2$". And they'll be focused on their own particular reduction, where $k=2$.

In short: you're right, yes, $k=2$ could be replaced with $k\ge 2$. But to the people writing that theorem, and most reading it, those really just feel like the same thing.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.