I'm interested in open questions from the book Approximation Algorithms for NP-Hard Problemss dedicated to k-clustering. They are:

Is Euclidean max cut solvable in polynomial time? If not, how well can it be approximated?

Does the problem minimizing the sum of distances from points to their cluster centers has good approximation algorithm ?


The problem of minimizing the sum of distances from points to cluster centers is called the $k$-median problem. In a general metric space, the $k$-median can be approximated to within a factor of $3+\epsilon$ and is $\mathsf{MAX SNP}$-hard. In Euclidean space, the problem admits a PTAS. This is a good survey and has references for the above facts.

| cite | improve this answer | |
  • $\begingroup$ Do you have a reference of the paper that show MAXSNP-hardness? The survey that you pointed out mentions this result but doesn't cite any paper. $\endgroup$ – Danu Sep 22 '11 at 20:50
  • 1
    $\begingroup$ dl.acm.org/citation.cfm?id=510012 (Jain/Mahdian/Saberi, STOC 2002) $\endgroup$ – Suresh Venkat Sep 22 '11 at 22:54

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.