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 ?