Is MAX CUT approximation resistant?

Question

CSP optimization problem is approximation resistant if it is $NP$-hard to beat the approximation factor of a random assignment. For instance, MAX 3-LIN is approximation resistant since a random assignment satisfies $1/2$ fraction of the linear equations but achieving approximation factor $1/2+ \epsilon$ is $NP$-hard.

MAX CUT is a fundamental $NP$-complete. It can be formulated as CSP problem of solving linear equations modulo 2 ($x_i + x_j= 1$ mod 2). A random assignment achieves $1/2$-approximation factor (of the total number of edges $|E|$). Haglin and Venkatesan proved that achieving an approximation factor $1/2+ \epsilon$ is $NP$-hard (i.e. finding a cut better than $|E|/2$). However, Hastad showed that MAX CUT is not approximable to $16/17+ \epsilon$ factor within the optimal cut unless $P=NP$. Goemans and Williamson gave a SDP-based polynomial time algorithm with 0.878 approximation factor (within the optimal cut) which is optimal assuming the Unique Games Conjecture. It seems to me that expressing the approximation factor relative to total number of constraints ($|E|$) is more natural and consistent with the convention used for MAX 3-LIN problem.

Why is the approximation factor for MAX CUT given relative to the size of optimal cut instead of the number of constraints (# of edges)? Am I right in concluding that MAX CUT is approximation resistant when the approximation factor is relative to the total number of constraints ($|E|$)?

Answer 1

If you measure approximation as a ratio between the number of constraints satisfied by your algorithm divided by the total number of constraints, then trivially all constraint satisfaction problems are unconditionally approximation-resistant.

By definition, a problem is approximation resistant if the (worst-case) approximation ratio of a random solution is (up to an additive $o(1)$ term) best possible among the (worst-case) approximation ratios achieved by all polynomial time algorithms.

With your definition of approximation ratio, you get approximation resistance of Max Cut (and all constraint satisfaction problems) just because you can always construct instances for which the ratio given (on average) by a random assignment is more or less (up to a $o(1)$ term) the same as the ratio given by an optimal assignment.

For example, in the Max Cut problem, a clique on $n$ vertices is a graph that has ${n \choose 2} = n\cdot (n-1)/2$ edges, and in which an optimal cut cuts $n^2/4$ edges. This means that every algorithm, and in particular every polynomial time algorithm, has a worst-case approximation ratio (according to your definition) that is at most $1/2 + O(1/n)$ on $n$-vertex graphs. The random assignment has ratio $1/2$ on all instances, and so no algorithm can do better than the random algorithm, and the problem is approximation-resistant.