# A greedy approximation algorithm for max k-cut

The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S_1,\cdots,S_k$ so that the total cost of edges running between these sets is maximized. The aim is to find a greedy algorithm for this problem that achieves a factor of $(1-\frac{1}{k})$.

My algorithm is: at the beginning, all the vertices of V is seperated in to $S_1,S_2,\cdots,S_n$. Once we have $S_1,\cdots,S_{t+1}$, we find $S_p,S_q$ s.t. $c(S_p,S_q)=min_{\{i,j\}}c(S_i,S_j)$ and merge $S_p,S_q$ together to get $t$ parts until $t=k$.
Let $ALG_t$ be the solution given by this algorithm for $t$ parts. $OPT_t$ is the optimum value for $t$ parts.
By induction, $ALG_n=OPT_n\ge(1-\frac{1}{n})OPT_n$.
Since there are $\binom{t+1}{2}$ sets of edges between $S_1,\cdots,S_{t+1}$, at least one of these sets with cost $\le\frac{1}{\binom{t+1}{2}}ALG_{t+1}$.
By the construction of the algorithm, we merge these two sets of vertices together, then we have $ALG_t\ge ALG_{t+1}-\frac{1}{\binom{t+1}{2}}ALG_{t+1}=(1-\frac{1}{\binom{t+1}{2}})ALG_{t+1}\ge(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})OPT_{t+1}\ge(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})OPT_{t}$
But it's not true that $(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})\ge(1-\frac{1}{t})$.
Therefore I wonder if there is some other arguments or algorithm?

• Try a different algorithm. Go vertex by vertex, and make the greedy choice. – Yuval Filmus Mar 5 '16 at 15:28