Comment:
If the triangle inequality is not satisfied the problem is called
MINIMUM EDGE DELETION
K-PARTITION.
Approximable within 1.7 for k=2 [213].
The maximization variation in which the subsets
must be
of equal size c is approximable within 2(c-1)/c or (c+1)/c,
depending on whether c is even or odd [160]
Moreover, if d does not satisfy the triangle inequality then the bounds are
c-1 and c, respectively [160];
the cases c=3 and c=4 are approximable within 2 [159].
Finally, if
required sizes
of the subsets are given and the triangle
inequality is satisfied then the maximization problem is approximable
within
[239].