Notices
Results 1 to 1 of 1

Thread: k means algorithm question

  1. #1 k means algorithm question 
    New Member
    Join Date
    Nov 2010
    Posts
    1
    Hi everyone! I'm new to the forum and I would like to receive some assistance on a problem that is troubling me. I've recently discovered the k-means algorithm for clustering, and I've been told that it is NP-hard for data dimensions higher than 2. My question is: how can I prove that the problem is not NP-hard when dimension is equal to 1 (points on a row)? The solution must have something to do with the fact that this kind of data can be sorted, but I can't find a mathematical proof. Any suggestion?


    Reply With Quote  
     

  2.  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •