8
$\begingroup$

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|$)?

$\endgroup$
  • $\begingroup$ Also, I'm wondering if Hastad's Max 3-LIN version of the PCP theorem can be inferred (directly or indirectly) from Haglin and Venkatesan in-approximability result of MAX CUT? $\endgroup$ – Mohammad Al-Turkistany Dec 17 '10 at 18:27
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Luca for your nice answer. It is not clear to me why the approximation factor of MAX 3-LIN (mod 2) is given relative to the total number of constraints (# of linear equations) instead of the optimal. $\endgroup$ – Mohammad Al-Turkistany Dec 19 '10 at 6:55
  • 3
    $\begingroup$ The negative results aren't: Hastad's hardness of approximation result is that, for every $\epsilon > 0$, it is NP-hard to find solutions that satisfy more than a $\frac 12 + \epsilon$ fraction of the equations satisfied by an {\em optimal} solution. (It would be trivial to say that there is no algorithm that always satisfies at least a $\frac 12 + \epsilon$ fraction of the constraints, think of the instance $x\oplus y \oplus z = 0; x \oplus y \oplus z = 1$). $\endgroup$ – Luca Trevisan Dec 20 '10 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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