<p>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. <a href="http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf" rel="nofollow">This is a good survey</a> and has references for the above facts. </p>

CC BY-SA 3.0
2011-09-22T20:50:56.213Z
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.
Dan
CC BY-SA 3.0
2011-09-22T22:54:30.163Z
http://dl.acm.org/citation.cfm?id=510012 (Jain/Mahdian/Saberi, STOC 2002)
Suresh Venkat
CC BY-SA 3.0
2011-09-21T15:17:03.517Z
2011-09-21T15:17:03.517Z
Suresh Venkat
<p>I'm interested in open questions from the book <a href="http://www.ieor.berkeley.edu/~hochbaum/html/book-aanp.html" rel="nofollow">Approximation Algorithms for NP-Hard Problems</a>s dedicated to k-clustering. They are:</p>

<blockquote>
  <p>Is Euclidean max cut solvable in polynomial time? If not, how well can
  it be approximated?</p>
  
  <p>Does the problem minimizing the sum of distances from points to their
  cluster centers has good approximation algorithm ?</p>
</blockquote>

<ds.algorithms><approximation-algorithms><clustering>
k-clustering problems
Kostia Antoniuk
# k-clustering problems

(Asked by: username_0 on 2011-09-21)

I'm interested in open questions from the book [Approximation Algorithms for NP-Hard Problems](http://www.ieor.berkeley.edu/~hochbaum/html/book-aanp.html)s 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 ?

**Tags:** ds.algorithms, approximation-algorithms, clustering

---

## 1 answers

### Answer by username_1 on 2011-09-21. Score: 7

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](http://www.cs.ucla.edu/~shindler/shindler-kMedian-survey.pdf) and has references for the above facts.

> **Comments:**
> **username_2**: 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.  
> **username_1**: http://dl.acm.org/citation.cfm?id=510012 (Jain/Mahdian/Saberi, STOC 2002)  

---

