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

The class Max (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 binary clauses, we present an O (n r 5 + 19 m / 100)-time algorithm which is the fastest polynomial...