Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You'd better explain what $w$ is. I thought at first that $w(u,v)$ would be the capacity of the edge between $u$ and $v$, but no, its first argument is a vertex and its second argument is a set of vertices, so that's not it. Is $w(v, S)$ the sum of the capacities of all the edges $(u,v)$ for $u\in S$? –  MJD May 20 '12 at 5:35
    
There; and that is how I understand it, though I'm not really much of an authority on the matter. –  Quail May 20 '12 at 6:37
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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