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?