Comment:
Not approximable within 1.058 for k=2 [226].
Not approximable within O(|E|) for
,
even for graphs with
for any
[271].
Approximable within 9/4 for planar graphs and k=2 [187].
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).