Re: NP-hardness of k-means clustering

From: Stas Busygin (busygin_at_a-teleport.com)
Date: 09/14/04 

Date: Tue, 14 Sep 2004 19:02:55 -0400

Hi Eray,

I checked the compendium first of all, and there are only two
clustering-related problems in Misc section:

http://www.nada.kth.se/~viggo/wwwcompendium/node126.html

Both of them are not about k-means.

Eray Ozkural exa wrote:
> busygin@a-teleport.com (Stas Busygin) wrote in message news:<8a5a72d7.0409071628.6be8cbf4@posting.google.com>...
>
>>Is there a published proof that the K-Centroid problem
>>is NP-hard?
>>
>>[K-Centroid Problem]
>>Given n points in R^m, find k other points in R^m
>>(centroids) such that the sum of distances from each
>>of the given points to its closest centroid is minimal.
>
>
> This seems to be the more general problem. Points in R^m is a special
> case.
>
> MINIMUM K-CENTER
> http://www.nada.kth.se/~viggo/wwwcompendium/node128.html

No, this is a different problem since it talks about "the
maximum distance" and the centers are given.

Best,

Stas
http://www.busygin.dp.ua