<p>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.</p>

<p>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. </p>

<p>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. </p>

<p>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. </p>

CC BY-SA 2.5
2010-12-19T06:55:24.647Z
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.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-20T18:57:41.813Z
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$).
Luca Trevisan
CC BY-SA 2.5
2010-12-19T03:47:14.640Z
2010-12-19T03:47:14.640Z
Luca Trevisan
<p>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.</p>

<p>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|$). <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=67327" rel="nofollow">Haglin and Venkatesan</a> 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. </p>

<blockquote>
  <p>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|$)?</p>
</blockquote>

CC BY-SA 2.5
2010-12-17T18:27:37.937Z
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?
Mohammad Al-Turkistany
<cc.complexity-theory><approximation-hardness><max-cut>
Is MAX CUT approximation resistant?
Mohammad Al-Turkistany
# Is MAX CUT approximation resistant?

(Asked by: username_0 on 2010-12-17)

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](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=67327) 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|$)?

**Tags:** cc.complexity-theory, approximation-hardness, max-cut

> **Comments:**
> **username_0**: 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?  

---

## 1 answers

### Answer by username_1 on 2010-12-19. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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$).  

---

