Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP

Alexander D. Scott, Gregory B. Sorkin

The class $(r,2)$-CSP, or simply Max 2-CSP, consists of constraint satisfaction problems with at most two $r$-valued variables per clause. For instances with $n$ variables and $m$…