Not approximable within 1.058 for k=2 .
Not approximable within
even for graphs with
Approximable within 9/4 for planar graphs and k=2 .
If G is the complete graph and w is required to satisfy the
triangle inequality, then the problem is called
MINIMUM K-CLUSTERING SUM (see Network Design).