<p>This is called the <em>edge-contraction heuristic</em>, in which an upper bound <span class="math-container">$(k-1)/(k+1)$</span> on the approximation ratio can be shown. See section 3 of <a href="http://www.inderscience.com/offer.php?id=17827" rel="nofollow noreferrer">the work by Kahruman et al.</a> for reference.</p>
<p>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 newly 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 <span class="math-container">$i$</span> edges being contracted (denoted as <span class="math-container">$W_i$</span>) satisfies the following inequality:</p>
<p><span class="math-container">$$W_i \leq \frac{2iW}{(n-1)(n-i-1)} \text{,}$$</span></p>
<p>where <span class="math-container">$W$</span> is the sum of weights of all edges.
This can be derived from
<span class="math-container">$$W_{i+1} \leq W_i + \frac{W-W_i}{({n-i\atop 2})} \text{,}$$</span>
since we always contract the lightest pair, the weight of the contracted edge cannot surpass the average weight.</p>
<p>One can see that the cut formed by this algorithm has weight <span class="math-container">$W_C = W-W_{n-k}$</span>,
and by observing that <span class="math-container">$W \geq W^*$</span> where <span class="math-container">$W^*$</span> is the weight of the optimum cut,
we have our desired approximation ratio:</p>
<p><span class="math-container">$$W_C \geq W-\frac{2(n-k)W}{(n-1)(k-1)} \geq \frac{k-1}{k+1}W^* \text{.}$$</span></p>
<p>For k=2, the algorithm gives a 1/3-approximation to the Max cut problem.</p>

CC BY-SA 3.0
2012-06-04T01:55:45.463Z
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?
Rahul Gopinath
CC BY-SA 4.0
2011-02-01T06:48:24.440Z
2020-11-25T09:54:07.300Z
2020-11-25T09:54:07.300Z
Hsien-Chih Chang 張顯之
<p>I'm thinking about an approximation algorithm for Max k-Cut. One simple and more involved approximation algorithms can be found <a href="http://www.math.cmu.edu/%7Eaf1p/Texfiles/cuts.pdf" rel="nofollow noreferrer">here</a>. The Max k-Cut problem is defined as follows.</p>
<blockquote>
<p>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 <em>maximized</em>.</p>
</blockquote>
<p>My algorithm is a greedy strategy and works as follow (maybe someone else already had a similar idea but I'm not aware of):</p>
<blockquote>
<p>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 <span class="math-container">$k$</span>.</p>
</blockquote>
<p>Is there a known approximation guarantee for this algorithm?</p>

CC BY-SA 2.5
2011-01-31T15:08:23.560Z
@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.)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-31T15:17:20.113Z
@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.
Saeed
CC BY-SA 2.5
2011-01-31T15:42:09.100Z
@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?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-31T15:54:52.037Z
@Saeed: Ah, now I get it. I'll try to modify the wording again.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-31T16:09:49.577Z
@Saeed: Is the current version consistent to the ideas in your mind?
Hsien-Chih Chang 張顯之
<ds.algorithms><graph-algorithms><approximation-algorithms><max-cut>
What's the approximation factor of this Max k-Cut approximation?
Saeed
# What's the approximation factor of this Max k-Cut approximation?

(Asked by: username_0 on 2011-01-31)

I'm thinking about an approximation algorithm for Max k-Cut. One simple and more involved approximation algorithms can be found [here](http://www.math.cmu.edu/%7Eaf1p/Texfiles/cuts.pdf). 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?

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, max-cut

> **Comments:**
> **username_1**: @username_0: 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.)  
> **username_0**: @username_1, 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.  
> **username_1**: @username_0: 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?  
> **username_1**: @username_0: Ah, now I get it. I'll try to modify the wording again.  
> **username_1**: @username_0: Is the current version consistent to the ideas in your mind?  

---

## 1 answers

### Answer by username_1 on 2011-02-01. Score: 15 | Accepted answer

This is called the *edge-contraction heuristic*, in 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.](http://www.inderscience.com/offer.php?id=17827) 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 newly 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.

> **Comments:**
> **username_2**: 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?  

---

