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?

  • $\begingroup$ Try a different algorithm. Go vertex by vertex, and make the greedy choice. $\endgroup$ Commented Mar 5, 2016 at 15:28

1 Answer 1


The natural greedy approach goes roughly like this:

Go over the vertices one by one. For each one, allocate it to a part in a way maximizing the total cost of edges cut.

There are at least two natural ways of defining total cost of edges cut:

  1. Total cost of edges between the vertex and vertices already allocated to different partitions.

  2. Same as 1, together with the expected cost of cut edges to vertices not already allocated.

In this case both ways are the same, but the second shows the connection between the greedy algorithm and the trivial randomized algorithm, which allocates the vertices completely randomly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.