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.

  • $\begingroup$ @Saeed: I'm not sure if I understand your question correctly, due to the grammar issue. (Unfortunately I'm not a native speaker either, so maybe we need some help from the English folks.) $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 31 '11 at 15:08
  • $\begingroup$ @Hsien-Chih Chang 張顯之, do you know a good graph designer (on web) to explain my algorithm with images? my problem is I have an approximation algorithm but I can't find approximation factor for it. $\endgroup$ – Saeed Jan 31 '11 at 15:17
  • $\begingroup$ @Saeed: Yes, I understand this part. The part I don't understand is the following sentence in your original version: "... or do you have any idea to how to come up with this problem (I'm talking about the algorithm I said not better algorithms which are available), I want to see is there tight approximation factor for this algorithm or not." Would you like to explain it? $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 31 '11 at 15:42
  • $\begingroup$ @Saeed: Ah, now I get it. I'll try to modify the wording again. $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 31 '11 at 15:54
  • $\begingroup$ @Saeed: Is the current version consistent to the ideas in your mind? $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 31 '11 at 16:09

This is called the edge-contraction heuristic, which an upper bound $(k-1)/(k+1)$ on the approximation ratio can be shown. See section 3 of the work by Kahruman et al. for reference.

Imagine whenever we combine two nodes u, v into a group, instead of forming a group we contract the edge (u, v) between these two nodes, and updates the weight of all the edges incident to the new formed node. Repeat the procedure until there are only k nodes left. Lemma 3.1 in the above paper shows that the sum of weights of the first i edges being contracted (denoted as $W_i$) satisfies the following inequality:

$$W_i \leq \frac{2iW}{(n-1)(n-i-1)} \text{,}$$

where $W$ is the sum of weights of all edges. This can be derived from $$W_{i+1} \leq W_i + \frac{W-W_i}{({n-i\atop 2})} \text{,}$$ since we always contract the lightest pair, the weight of the contracted edge cannot surpass the average weight.

One can see that the cut formed by this algorithm has weight $W_C = W-W_{n-k}$, and by observing that $W \geq W^*$ where $W^*$ is the weight of the optimum cut, we have our desired approximation ratio:

$$W_C \geq W-\frac{2(n-k)W}{(n-1)(k-1)} \geq \frac{k-1}{k+1}W^* \text{.}$$

For k=2, the algorithm gives a 1/3-approximation to the Max cut problem.

| cite | improve this answer | |
  • $\begingroup$ I do not seem to understand the last crucial step. i.e $$1-\frac{2(n-k)}{(n-1)(k-1)} \geq \frac{k-1}{k+1}$$, no terms seem to cancel out, could you please explain? $\endgroup$ – rahul Jun 4 '12 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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