2
$\begingroup$

The Johnson-Cut is an $O(n^2)$ Max-Cut approximation with a factor of 2. I have these definitions for MC and none for JC so I assume they're the same:

$G = (V,E,w)$ with $|V| = n$ and $w : E \rightarrow Q^+$

Maximize $w(V_1,V_2) = \sum_ {v_1 \in V_1, v_2 \in V_2} w(v_1,v_2)$

The algorithm is

JohnsonCut(G = (V,E,w))     V1,V2 := ∅;     for v ∈ V do         if w(v,V1) > w(v,V2) do             V2 := V2 ∪ {v}         else             V1 := V1 ∪ {v}         fi     od     return (V1,V2) 

My intuition tells me this means that $MC/2 \leq JC \leq MC$ (rather than $JC \leq 2MC$) but the proof eludes me. It is evident that the algorithm isn't performing anywhere near enough comparisons for optimality but why is it performing enough to guarantee a factor of 2?

  • 0
    There; and that is how I understand it, though I'm not really much of an authority on the matter.2012-05-20

1 Answers 1

1

OK, so if $w(v,V_x) = \sum_ {v \notin V_1 \cup V_2, v_x \in V_x} w(v,v_x)$ we can look at what the cut for each iteration will yield.

The first vertex we look at will of course be added to $V_1$, both $V_1$ and $V_2$ are empty sets, so $w(v,V_x)$ will return 0 in both calls.

Note that we only look at each edge once (if an edge goes to neither set, we don't bother with it yet). This is the key to it all.

$v$ is the vertex we are examining in the current iteration.
Name the sum of the weight of all edges of $v$ that go to $V_1$ $w_{v_1}$ and all that go to $V_2$ $w_{v_2}$. $z$ is the cut we are going to choose and $w_z$ its weight.

Clearly $w_z \geq (w_{v_1} + w_{v_2})/2$ (hint: set $z=v_1$, times 2 minus $w_{v_1}$).

The sum of all our cuts would then be: $\sum{w_z} \geq \frac{\sum{w_{v_1}+ w_{v_2}}}{2}$

The sum of the weight of all the edges in the graph is $W$. The Max-Cut result can of course not be greater than that.
Because we are only looking at each edge exactly once we know that $W=\sum{w_{v_1} + w_{v_2}}$.
Ergo $\sum{w_z} \geq \frac{W}{2}$

The running time should be $O(n^2)$. We look at $n$ vertices, but each of them can have edges to $n - 1$ other vertices.