Every 2-CSP allows nontrivial approximation

We use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does provably better than picking a random assignment. To be more precise assume that each variable can take values in [d] and that each constraint rejects t out of the d 2 possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, on expectation, within a factor (1- t/d 2 (1- c/d 2 log d)) of optimal.

Authors

• Johan Håstad

Keywords

• approximation algorithms
• constraint satisfaction
• semi-definite programming