- INSTANCE: Graph and a weight function .
- SOLUTION:
A
*k*-partition, i.e., a color assignment . - MEASURE:
The weight of the monochromatic edges, i.e.,
.

*Good News:*Approximable within for*k=2*[189] and within for*k=3*and any [286].*Bad News:*Not in APX[426].*Comment:*Not approximable within 1.058 for*k=2*[242]. Not approximable within for , even for graphs with for any [286]. Approximable within 9/4 for planar graphs and*k=2*[199]. 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).