Approximation of non-boolean 2CSP

Guy Kindler, Alexandra Kolla, Luca Trevisan

We develop a polynomial time $\Omega \left(\frac{1}{R}\log R\right)$ approximate algorithm for Max 2CSP-$R$, the problem where we are given a collection of constraints, each involving t…