Some optimal inapproximability results
Johan Håstad · Journal of the ACM · 1997
We prove optimal, up to an arbitrary ε > 0, inapproximability results for Max-E k -Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.