Re: NP-hardness of k-means clustering

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 09/09/04 

Date: 9 Sep 2004 02:41:12 -0700

Stas Busygin <busygin@a-teleport.com> wrote in message news:<TSB%c.75413$N11.62620@bignews5.bellsouth.net>...
> 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.
> >
> >
> > It's well known that it's NP-complete for L2-norm, but I don't
> > remember any reference, you can talk about it as folklore in your
> > paper I guess.
>
> No, I'm interested to see the NP-hard problem which was reduced
> to K-Centroids.

Ok. The only reference I can remember that talks about its
NP-completeness is Vapnik's Support Vector Clustering paper, but that
doesn't give a ref. either, IIRC.

There are some lists of NP-complete problems on the web. This one I
particularly like:
http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html

Oh, here it is:

Number: 85
Name: Clustering [MS9] 3

Input: Finite set X; for each pair of elements x and y in X, a
positive integer distance d(x,y); positive integer B.

Question: Is there a partition of X into 3 disjoint sets - X1,X2,X3 -
with which: for each set Xi (1<=i<=3), for all pairs x and y in Xi it
holds that d(x,y)<=B?

And in the essential source, your problem is given as (minimum sum of
squares):
http://www.nada.kth.se/~viggo/wwwcompendium/node155.html

You may follow the refs there.

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: NP-hardness of k-means clustering
    ... The only reference I can remember that talks about its ... doesn't give a ref. ... Finite set X; for each pair of elements x and y in X, ... positive integer distance d; positive integer B. ...
    (sci.math)
  • Re: Passing arguements by reference
    ... but doSomething doesnt change p unless i use "ref"? ... reference, hence both p and q pointing to the same object, not to different ... don't use the ref keyword. ... void Execute() ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Documentation suggestions
    ... > Ian> I think it would be very useful if there was reference (not just ... Lang ref as only for "language lawyers". ...
    (comp.lang.python)
  • Re: pass by reference
    ... focus has moved from insisting to use "by ref" in java-context ... independent of any other use of the word "reference" in a language. ... Just because Java-refs can be re-targetted by assignment? ... If Java had an operator to tell an Object ...
    (comp.lang.java.programmer)
  • Re: Texas TMS1232 Delta Sigma converters
    ... John Larkin writes: ... >>picked up between the transducer and the ADC I'm trying to eliminate. ... the reference problem is serious. ... We're using an Analog Devices Xfet ref, ADR421, ...
    (sci.electronics.design)