Approximation of non-boolean 2CSP
Guy Kindler, Alexandra Kolla, Luca Trevisan · 2015
We develop a polynomial time Ω ( log R) approximate algorithm for Max 2CSP-R, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size R, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the best possible approximation up to constant factors. Previously, a 1/R-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming. The Semidefinite Program that we use has an almost-matching integrality gap. For the more general Max kCSP-R, in which each constraint involves k variables, each ranging over a set of size R, it was known that the best possible approximation is of the order of k/Rk – 1, provided that k is sufficiently large compared to R; our algorithm shows that the bound k/Rk – 1 is not tight for k = 2.