I'm thinking about an approximation algorithm for Max k-Cut. One simple and another one advance approximation algorithms are available here. The Max k-Cut problem is defined as follow:
Assume we have a graph G = (V, E) and given k, n = |V|, the problem is to partition G into k disjoint sets such that the number of edges between disjoint parts is maximized.
My algorithm is a greedy strategy and works as follow (maybe someone have a similar idea to this and I didn't read it):
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.
Are there known approximation guarantees for this algorithm ?
I want to see whether a tight approximation factor for this algorithm exist or not. (I'm thinking this just for the enjoyment of math, nothing else). Also if you have any good but not so tight factors I'll be thankful to see it.