Besides complete graphs, other special classes of graphs have been
considered, including complete \(k\) -partite
graphs [1]}, [2]} and the weighted case where
the weights of \(-\) edges satisfy the triangle
inequality [3]}. The result for complete
\(k\) -bipartite graphs match the integrality gap of the standard
LP. When the number of clusters \(k\)  is bounded, Giotis and
Guruswami [4]} and Karpinski and
Schudy [5]} showed that a PTAS exists.
