Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? 2: Random-Hyperplane Rounding Approximates Balanced MAX-2SAT within β ≈ 0.943Research Paper
MAX-2SAT asks for an assignment of Boolean variables that maximizes the total weight of satisfied clauses, each clause being a disjunction of two literals. It is one of the basic constraint satisfaction problems of approximation theory, and its approximability has been studied alongside MAX-CUT since semidefinite programming entered the field.