5
$\begingroup$

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 ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2011 at 20:50
  • 1
    $\begingroup$ dl.acm.org/citation.cfm?id=510012 (Jain/Mahdian/Saberi, STOC 2002) $\endgroup$
    – Suresh Venkat
    Sep 22, 2011 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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