(This is a cross-post from the Theoretical Computer Science Stack Exchange.)
For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any other cut. Finding a max cut is NP-hard, but a greedy algorithm (e.g.) can approximate a max cut, finding a cut with at least half as many edges as possible.
Equivalently, a cut $\delta (S)\subseteq E(G)$ is a max cut if and only if $$| \delta (S)\cap \delta (T) |\geq \frac{1}{2}|\delta (T)| \qquad \forall\text{ cuts } \delta (T)\subseteq E(G).$$ Proof: It should be clear that the standard definition implies this one. To show that these inequalities imply $\delta (S)$ is at least as big as any other cut $\delta (S')$, observe that $$|\delta (S)| - |\delta (S')| = |\delta (S) \cap \delta (S\Delta S')| - |\delta (S') \cap \delta (S\Delta S')|.$$ Because the two edge-sets appearing in the right-hand side partition the edges of the cut $\delta (S\Delta S')$, applying the above inequality with $S\Delta S'$ in the role of $T$ gives $|\delta (S)|-|\delta (S')|\geq 0$. $\square$
I'd like to know whether max cuts can be easily approximated in the sense of my second definition. Specifically:
Question: Is there a polynomial-time algorithm to find a cut $\delta (S)\subseteq E(G)$ with $$| \delta (S)\cap \delta (T) |\geq \epsilon |\delta (T)| \qquad \forall\text{ cuts } \delta (T)\subseteq E(G)$$ for some $\epsilon > 0$?
