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 ?
k-clustering problems
ds.algorithms;approximation algorithms;clustering