k-clustering problems 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.