I'm thinking about an approximation algorithm for Max k-Cut. One simple and more involved approximation algorithms can be found here. The Max k-Cut problem is defined as follows.
Input is a graph G = (V, E) and an integer k, n = |V|, the question asks for partitioning G into k disjoint sets such that the total number of edges between disjoint parts is maximized.
My algorithm is a greedy strategy and works as follow (maybe someone else already had a similar idea but I'm not aware of):
Start with each vertex in a group by itself, and at each step, combine the two groups that have a minimum number of edges between them. Repeat this until the number of groups shrinks to $k$.
Is there a known approximation guarantee for this algorithm?